第七届蓝桥杯决赛 赢球票_赢球票c++-CSDN博客

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

　　首先考虑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 imes(m-5) imes(m-1)! imes7 imes(n-8) imes(n-1)! imes{(m-5+n-8)!over(m-5)!(n-8)!}

　　$$

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