题目描述
某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
输入输出格式
输入格式：
只有一行且为用空格隔开的两个非负整数 n 和 m，其含义如上所述。 对于 30%的数据 n<=100,m<=100 对于 100%的数据 n<=2000,m<=2000
输出格式：
输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。
输入输出样例
输入样例#1：
1 1
输出样例#1：
12
Solution：
本题组合数学+高精度。
冷静分析。。。
首先$n$个男生的全排列为$A(n,n)$，在形成的$n+1$个空中插入两名老师方案数为$A(n+1,2)$，新形成的$n+3$个空中选择$m$个插入女生方案数为$A(n+3,m)$。
注意到上面的情况并没有包含两名老师夹一个女生的情况，我们需要补上该情况的方案：把两名老师和一个女生看作整体，有$A(2,2)*m$种方案，然后把这个整体插入到$n+1$个空中有$A(n+1,1)$种方案，最后的$m-1$个女生插入到$n+2$个空中方案数为$A(n+2,m-1)$。
综上所述，总的方案数为$A(n,n)*A(n+1,2)*A(n+3,m)+m*A(2,2)*A(n+1,1)*A(n+2,m-1)$，然后需要用到高精度加法和乘法，结构体重载运算符就好了。
代码：
/*Code by 520 -- 9.13*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const ll N=,Base=1e8;
ll n,m;
struct node{
ll a[N],len;
il void Clr(){memset(a,,sizeof a),len=;}
il void Push(int x){a[len=]=x;}
node operator * (const node &X) const{
node tp;tp.Clr();tp.len=len+X.len+;
For(i,,len) For(j,,X.len) {
tp.a[i+j-]+=a[i]*X.a[j];
tp.a[i+j]+=tp.a[i+j-]/Base;
tp.a[i+j-]%=Base;
}
For(i,,tp.len) tp.a[i+]+=tp.a[i]/Base,tp.a[i]%=Base;
while(tp.len&&!tp.a[tp.len]) tp.len--;
return tp;
}
node operator + (const node &X) const{
node tp;tp.Clr();tp.len=max(len,X.len)+;
For(i,,tp.len){
tp.a[i]+=a[i]+X.a[i];
tp.a[i+]+=tp.a[i]/Base;
tp.a[i]%=Base;
}
For(i,,tp.len) tp.a[i+]+=tp.a[i]/Base,tp.a[i]%=Base;
while(tp.len&&!tp.a[tp.len]) tp.len--;
return tp;
}
il void Output(){
printf("%lld",a[len]);
Bor(i,,len-) printf("%08lld",a[i]);
}
}ans; il node A(ll n,ll m){
node res,tp;res.Clr(),tp.Clr(),res.Push();
if(!m) return res;
if(m>n) {ans.Clr();return res;}
For(i,n-m+,n) tp.Push(i),res=res*tp;
return res;
} int main(){
cin>>n>>m;
if(!n&&!m) cout<<,exit();
ans=A(n,n)*A(n+,)*A(n+,m)+A(n,n)*A(n+,)*A(,)*A(m,)*A(n+,m-);
ans.Output();
return ;
}