一场球赛开始前，售票工作正在紧张进行中。每张球票为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]`。

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票 主持人拿出N张卡片(上面写着1··N的数字)，打乱顺序，排成一个圆圈你可以从任意一张卡片开始顺时针数数:123 如果数到的数字刚好和卡片上的数字相同，则把该卡片收入雾中，从下一个卡片重新数数。 直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数. 比如: 卡片排列是:123 我们从1号卡开始数，就把1号卡拿走。再从2号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了1张球票 还不算太坏!如果我们开始就傻傻地从2或3号卡片数起，那就一张卡片都拿不到1o 如果运气好，卡片排列是213，那我们可以顺利拿到所有的卡片! 本题的目标:已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票

这是一个经典的约瑟夫问题，可以使用数学方法进行求解。假设卡片排列是1, 2, 3, ..., N，我们从第K张卡开始数，每次数M个，那么最后剩下的卡片编号为：

((K-1)+M) % N + 1, ((K-1)+2M) % N + 1, ((K-1)+3M) % N + 1, ..., ((K-1)+(N-1)M) % N + 1

为了使得拿到的卡片数最多，我们需要找到一个最大的M，使得所有剩下的卡片编号之和最大。这个问题可以通过枚举K和M来解决，时间复杂度为O(N^2)。但是还有更快的算法。

首先，我们可以把问题转化为求剩下的卡片编号之和最小。这是因为，如果我们从第K张卡开始数，每次数M个，拿到的卡片编号和为S，那么剩下的卡片编号和就是1+2+...+N-S，也就是(N+1)N/2-S。因此，如果我们能找到一个最小的剩下卡片编号和，就可以通过(N+1)N/2减去它得到拿到的卡片编号和的最大值。

接下来，我们考虑如何快速求解剩下的卡片编号之和的最小值。假设我们从第i张卡开始数，每次数M个，得到的剩余卡片编号为：

(i+M-1) % N + 1, (i+2M-1) % N + 1, ..., (i+(N-1)M-1) % N + 1

我们可以把它们按照卡片编号从小到大排序，得到一个新的序列：

j1, j2, ..., jN

其中，j1, j2, ..., jN是1, 2, ..., N的一个排列，满足：

(i+(j1-1)M) % N + 1 <= (i+(j2-1)M) % N + 1 <= ... <= (i+(jN-1)M) % N + 1

我们把这个排列称为“最小化序列”。注意到，不同的i和M得到的最小化序列可能不同，但是它们都可以通过某种旋转方式相互转化。因此，我们只需要找到最小化序列中的最小值，即可得到剩下的卡片编号之和的最小值。

接下来，我们考虑如何快速求解最小化序列中的最小值。假设最小化序列为：

j1, j2, ..., jN

我们把它扩展成一个长度为2N的序列：

j1, j2, ..., jN, j1, j2, ..., jN

然后，我们可以使用动态规划的方法求解最小值。令f(i,j)表示从序列中的第i个位置开始，长度为j的子序列中的最小值。显然，f(i,j)可以通过f(i,j/2)和f(i+j/2,j/2)求解。具体地，我们可以考虑分两种情况：

1. 最小值在序列的前半部分。这意味着从第i个位置开始，长度为j的子序列至少包含前半部分的一个元素，即j1, j2, ..., jN中的某个元素。因此，我们可以枚举这个元素，然后在序列的前半部分中查找它的位置，从而得到f(i,j/2)。

2. 最小值在序列的后半部分。这意味着从第i个位置开始，长度为j的子序列至少包含后半部分的一个元素，即j1, j2, ..., jN中的某个元素。因此，我们可以枚举这个元素，然后在序列的后半部分中查找它的位置，从而得到f(i+j/2,j/2)。

最终的答案就是(N+1)N/2减去剩下卡片编号之和的最小值。

代码实现如下：