一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。这m+n个人排队购票时，特别规定第5位为持50元，第8位为持100元，求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数 。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）

这个问题需要使用组合方法进行计算。

首先考虑50元的顾客，假设他们排成一个有序队列，记为$A_1,A_2,\cdots,A_m$。第5位必须是$A_5$，那么他前面有4种选择，后面有$m-5$种选择。其他$m-1$个50元顾客没有限制，可以随意排列，共有$(m-1)!$种排列方式。

同理，考虑100元的顾客，假设他们排成一个有序队列，记为$B_1,B_2,\cdots,B_n$。第8位必须是$B_8$，那么他前面有7种选择，后面有$n-8$种选择。其他$n-1$个100元顾客没有限制，可以随意排列，共有$(n-1)!$种排列方式。

现在需要把$A_1,A_2,\cdots,A_m$和$B_1,B_2,\cdots,B_n$合并成一个队列，使得每个50元顾客前面都是50元顾客，每个100元顾客前面都是50元顾客。考虑将$A_5$和$B_8$插入到队列中间的过程，相当于将$m-5$个50元顾客和$n-8$个100元顾客插入到$m+n-2$个空隙中（这个数目等于队列总人数减去已经插入的顾客数目）。空隙的数目为$m+n-1$个，插入顺序可以任意排列，所以插入的方案数为$(m-5+n-8)!\over(m-5)!(n-8)!$。

最终答案为$$
4\times(m-5)\times(m-1)!\times7\times(n-8)\times(n-1)!\times{(m-5+n-8)!\over(m-5)!(n-8)!}
$$

注意到$m$和$n$的范围比较小，可以直接枚举，时间复杂度为$O(m^2n^2)$。

相关问题

5. 常规排队 一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数 。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）请用递归和递推两种方法完成。

递归方法：

假设当前售票处有 `a` 元钱，当前有 `m` 个人手持50元的钞票和 `n` 个人手持100元的钞票在排队购票，我们考虑以下两种情况：

1. 当前没有人排队购票，此时售票处的钱数为 `a` 元，方案数为1。
2. 当前有人排队购票，我们可以将第一个人的钞票面额分为两种情况：50元和100元。

- 如果第一个人手持50元的钞票，那么售票处的钱数变为 `a+50`，排队的人数变为 `m-1` 和 `n`，此时的方案数为 `f(a+50, m-1, n)`。

- 如果第一个人手持100元的钞票，那么售票处的钱数变为 `a-50`，排队的人数变为 `m-1` 和 `n+1`，此时的方案数为 `f(a-50, m-1, n+1)`。

所以，对于给定的 `a`、`m` 和 `n`，方案数为 `f(a, m, n) = f(a+50, m-1, n) + f(a-50, m-1, n+1)`。

递推方法：

我们可以使用一个三维数组 `dp`，其中 `dp[i][j][k]` 表示售票处有 `i` 元钱，当前有 `j` 个人手持50元的钞票和 `k` 个人手持100元的钞票在排队购票时的方案数。

边界条件：当售票处有0元钱时，方案数为1。

状态转移方程：对于每个状态 `(i, j, k)`，我们考虑以下两种情况：

1. 如果还有50元的钞票未处理，则可从状态 `(i+50, j-1, k)` 转移过来，方案数加上 `dp[i+50][j-1][k]`。
2. 如果没有50元的钞票了，则必须从状态 `(i-50, j-1, k+1)` 转移过来，方案数加上 `dp[i-50][j-1][k+1]`。

最终答案为 `dp[0][m][n]`。