题目描述
某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
输入输出格式
输入格式：
只有一行且为用空格隔开的两个非负整数 n 和 m，其含义如上所述。 对于 30%的数据 n<=100,m<=100 对于 100%的数据 n<=2000,m<=2000
输出格式：
输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。
输入输出样例
输入样例#1：
1 1
输出样例#1：
12
考虑将老师和女生放到男生中间(注意这道题每个人不一样)
男生排列方案：A(n,n)
现在有n+1个间隔，要将2个老师放入：A(n+1,2)
现在产生了n+3个间隔，将m个女生放入：A(n+3，m) 但是我们忽略了一种方案
我们算的是将老师分别放到男生中间，也就是说，隔开老师的必有一个男生
实际上可以只放一个女生
把2个老师和1个女生和为一块，放入男生中方案:n+1
放剩下的女生：A(n+2,m-1)
选出1个女生：C(m,1)
老师排列方案：A(2,2)=2
男生排列方案：A(n,n)
所以ans=A(n,n)*A(n+1,2)*A(n+3,m)+(n+1)*A(n+2,m-1)*C(m,1)*A(n,n)*2
因为不取模，所以必须要高精度
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int ans1[],ans2[],ans[],len1,len2,len;
int n,m;
void calc1(int x)
{int i;
for (i=;i<=len1;i++)
{
ans1[i]*=x;
}
for (i=;i<=len1;i++)
if (ans1[i]>=)
{
ans1[i+]+=ans1[i]/;
ans1[i]%=;
}
while (ans1[len1+])
{
len1++;
if (ans1[len1]>=)
{
ans1[len1+]+=ans1[len1]/;
ans1[len1]%=;
}
}
}
void calc2(int x)
{int i;
for (i=;i<=len2;i++)
{
ans2[i]*=x;
}
for (i=;i<=len2;i++)
if (ans2[i]>=)
{
ans2[i+]+=ans2[i]/;
ans2[i]%=;
}
while (ans2[len2+])
{
len2++;
if (ans2[len2]>=)
{
ans2[len2+]+=ans2[len2]/;
ans2[len2]%=;
}
}
}
void add()
{int i;
len=max(len1,len2);
for (i=;i<=len;i++)
ans[i]=ans1[i]+ans2[i];
for (i=;i<=len;i++)
if (ans[i]>=)
{
ans[i+]+=ans[i]/;
ans[i]%=;
}
while (ans[len+])
{len++;
if (ans[len]>=)
{
ans[len+]+=ans[len]/;
ans[len]%=;
}
}
}
int main()
{int i;
cin>>n>>m;
ans1[]=;len1=;
for (i=;i<=n;i++)
calc1(i);
calc1(n+);calc1(n);
for (i=n+;i>=n+-m;i--)
calc1(i); ans2[]=;len2=;
calc2(n+);
for (i=n+;i>=n+-m;i--)
calc2(i);
calc2(m);
for (i=;i<=n;i++)
calc2(i);
calc2();
add();
for (i=len;i>=;i--)
printf("%d",ans[i]);
}