排队题解
-
题目
某中学有 𝑛名男同学，𝑚 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
- 思路分析
考虑使用插板法 先不考虑两位老师,相当于 n+3 个空中插 m 个板，总方案数为：
A_{n+2}^{n+2}*A_{m}^m*C_{n+3}^m再使用捆绑法，把两位老师当作一名男同学,相当与 n+2 个空中插 m 个板，总方案数为：
A_2^2*A_{n+1}^{n+1}*A_{m}^m*C_{n+2}^m两者相减即是答案(注意C++得使用高精度)
import sys
import math
ans=0
n,m=map(int,input().split())
def f(x):
return math.factorial(x)
def A(x,y):
return f(x)//f(x-y)
def C(x,y):
return f(x)//(f(x-y)*f(y))
ans+=A(n+2,n+2)*A(m,m)*C(n+3,m)
ans-=2*A(n+1,n+1)*A(m,m)*C(n+2,m)
print(ans)