排队买票（两种方法）

解题思路:

思路一：实打实的对所有可能的排列做判断。

思路二：不考虑每位小孩的差异性，仅找出满足条件的序列，然后根据1元小孩所占的坑位和2元小孩所占的坑位，让他们在自己的坑位自由排列，最终将三个数相乘即可得到结果。即（一元小孩阶乘）*（二元小孩阶乘）*（满足条件的序列数量）。

若代码逻辑或者编码习惯有应该修改的地方请大家斧正！不胜感激！

注意事项:记录一下我踩得坑，一开始我直接用的全排列函数permutations()，这种方法必须先把矩阵存下来，导致空间复杂度太高，达到了200多M，直接不能通过，我python又用的不咋地，没法对原方法修改，只能换方法。后来只能自己写了全排列方法，并每求出一个排列就进行判断，这种方法降低了空间复杂度，但是时间复杂度依旧过高，在进行提交的时候显示时间过长，我这改改那改改都不成功，最终学人家的方法确定首位为一，再对m-1进行全排列，才勉强过关。再然后就是思路二学人家的方法，这个蛮好的。

参考代码:

思路一

w,n,k=map(int,input().split())
m=[1]*(n-1)+[2]*k
sum1=0
def perm(m,p):#全排列并进行判断
   if p==w-1:#当p指针超出范围则代表当前序列已确定
       panduan(m)
       return
   for i in range(p,w-1):#依次将w-1个小孩固定在当前位置，该位置由递归深度决定（之所以为w-1，是因为直接确定第一位为1位1元小孩，可以减少大量计算）
       t=m[i]#小孩位置的替换
       m[i]=m[p]
       m[p]=t
       perm(m,p+1)#进行全排列
       t=m[i]#全排列完毕后将小孩替回来，避免出现重复情况
       m[i]=m[p]
       m[p]=t
def panduan(i):#对当前序列进行判断
   global sum1
   k=1#默认为一，减少计算复杂度
   if i==[]:#防止1 1 0的情况
       sum1+=1
       return
   for j in range(len(i)-1,-1,-1):#对序列从尾部开始判断，k记为当前售货员手中一元纸币的数量
       if i[j]==1:#该小孩为一元小孩则1元纸币加一
           k+=1
       else:
           i[j]==2#该小孩为两元小孩则1元纸币加一
           k-=1
       if k<0:
           return
       if j == 0:#若最后一位小孩交完钱，则该序列为成功
           sum1+=1
           return
if n<k:#若一元小孩数量小于两元小孩数量则直接失败
   print(sum1)
else:
   perm(m,0)
   print(sum1*n)#由于第一位小孩已确定必须是一位1元小孩，所以仅需要对后面m-1为小孩进行全排列判断，再乘一元小孩的数量即可

思路二

from math import factorial
m,n,k=map(int,input().split())
sum1=0
def fun(one,n,k):#one为当前售票员手中1元的数量，n、k分别为一元和两元的数量
   if one<0 or n<0:#遇到1元为负的情况，直接返回0
       return 0
   if  k==0 and n>=0:#由于一元的数量大于等于两元的数量，所以两元必定先到0，一元不一定。
       return 1
   if not one :#若当前售票员手中一元的数量为0，则不考虑接下来为两元的情况，直接考虑下一位为一元
       return fun(one+1,n-1,k)
   return fun(one+1,n-1,k)+fun(one-1,n,k-1)#每个位置有两种可能
if(n<k):print(sum1)#若一元纸币数量小于两元纸币数量，则必定失败
else:
   print(fun(0,n,k)*factorial(n)*factorial(k))#结果等于合法的情况（即不考虑小朋友的差异，只考虑哪个位置该1，哪个位置该2） *n!
   # （即在n个坑位1元小孩的自由排列）*k！(在m个坑位2元小孩的自由排列)