公式:A(n,n)*A(n+1,2)*A(n+3,m) +    A(n,n)*C(m,1)*A(2,2)*C(n+1,1)*A(n+2,m-1)
分情况讨论推出公式
前者为无论何时都合法的,后者为先不合法,然后再合法的(两个老师先站在一 起,然后一个女生
插进来,所以要把这3个人看成一个整体,然后老师可以左右换,所以乘2,女生 就是m选1,然后整体再插入队伍
最后得到上面的式子
由于答案较大,所以要写高精
 #include<bits/stdc++.h>
using namespace std;
#define AC 10000
#define R register int
#define D printf("the k is %d\n",k);
/*A(n,n)*A(n+1,2)*A(n+3,m) + A(n,n)*C(m,1)*A(2,2)*C(n+1,1)*A(n+2,m-1)
分情况讨论推出公式
前者为无论何时都合法的,后者为先不合法,然后再合法的(两个老师先站在一 起,然后一个女生
插进来,所以要把这3个人看成一个整体,然后老师可以左右换,所以乘2,女生 就是m选1,然后整体再插入队伍
最后得到上面的式子
*/
int sum2[AC],a[AC],sum1[AC],k,n,m,tot,tot1,tot2,ans[AC];//每次计 算前将memset a,将高精sum*低精k存入a,然后计算完毕后将a导入sum void ADD()//加法
{
for(R i=;i<=max(tot1,tot2);i++)//error!!!注意这里要加到max(tot1,tot2)!!!
{
ans[i+]=ans[i+]+(sum1[i]+sum2[i]+ans[i])/;
ans[i]=(ans[i]+sum1[i]+sum2[i])%;
}
tot=(tot1+tot2)%;
while(!ans[tot] && tot>)--tot;//注意边界!!!
} void add1()//乘法1,计算前一部分
{
memset(a,,sizeof(a));
for(R i=;i<=tot1;i++)
{
a[i+]=a[i+]+(a[i]+sum1[i]*k)/;
a[i]=(a[i]+sum1[i]*k)%;
}
tot1+=;//因为n和m最大就是2000,所以最多也就加这么多位了,又因为压了位,,,所以
while(!a[tot1] && tot1>)--tot1;
if(!a[tot1])memset(sum1,,sizeof(sum1));//如果女生太多了会导致没有合法情况!!
else for(R i=;i<=tot1;i++) sum1[i]=a[i];//导入sum
} void add2()//乘法2,计算后一部分
{
memset(a,,sizeof(a));
for(R i=;i<=tot2;i++)
{
a[i+]=a[i+]+(a[i]+sum2[i]*k)/;
a[i]=(a[i]+sum2[i]*k)%;
}
tot2+=;//因为n和m最大就是2000,所以最多也就加这么多位了,又因为压了位,,,所以
while(!a[tot2] && tot2>)--tot2;
if(!a[tot2])memset(sum2,,sizeof(sum2));
else for(R i=;i<=tot2;i++) sum2[i]=a[i];//导入sum
} void work()
{
sum1[]=;//初始值
tot1=;
for(R i=;i<=n;i++)//计算A(n,n),即n!
{
k=i;
add1();
}
k=n;
add1();
k=n+;//分开乘,不然k太大会爆
add1();
k=n+;
for(R i=;i<=m;i++)//计算A(n+3,m)
{
add1();
--k;
}
//一二部分分割线~~~~~~~~~~~~~~~
sum2[]=*(n+);//不会破万,所以直接放在第一个即可
tot2=;
k=m;
add2();
for(R i=;i<=n;i++)
{
k=i;
add2();
}
k=n+;
for(R i=;i<=m-;i++)
{
add2();
--k;
}
ADD();//最后把sum1和sum2相加得到ans
printf("%d",ans[tot--]);
for(R i=tot;i>=;i--)printf("%04d",ans[i]);
/*printf("\n");
while(!sum1[tot1])tot1--;
printf("%d",sum1[tot1]);
for(R i=tot1-1;i>=1;i--)printf("%04d",sum1[i]);*/
} int main()
{
freopen("in.in","r",stdin);
scanf("%d%d",&n,&m);
work();
fclose(stdin);
return ;
}
 
05-21 08:20