「题解」：[组合数学]：排队

题目描述：n个男生，m个女生，2名老师，任意两名女生不能相邻，两名老师不能相邻，求解排列方法数。

题解：典型的插板法，

n个男生先放进去A(n,n)，

然后插入老师，n+1个空位插入2名老师，$A_{n+1}^2$，

最后插入m名女生，A(n+3,m)。

然而并不对。

考虑考虑我们漏掉了什么重要的东西？

显然上面的情形老师之间必然有男生。

那么可不可以两名老师仅由女生隔开呢？

显然是可以的。而上面的情形并不包含这种情况（两名老师之间必有男生）

如果两名老师之间仅有女生隔开的话，那么他们之间只有一名女生（女生不能相邻）

所以我们再加上这种情况就好啦！

先选出一名女生放在老师之间。

然后把两名老师和他们中间的女生看作一个男生。

老师的位置可以互换，情况为m*2。

然后把这n+1名男生排列一下A(n+1,n+1)。

然后把m-1名女生插入n+1名男生之间A(m-1,n+2)。

完美！

放代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define rint register int
using namespace std;
int m,n;
int ans1[10000008],ans2[10000008],c[10000008];
/*inline long long dc(int x)
{
    long long ans=1;
    for(register long long i=x;i>=1;i--)
        ans*=(long long)i;
    return ans;
}*/
inline void add(int a[],int b[])
{
    for(int i=1;i<=a[0]||i<=b[0];i++) 
    { 
        int x=0;
        c[i]+=a[i]+b[i];
        if(c[i]>=10)
        {
            c[i]%=10;
            x++;
        }
        c[i+1]+=x;
        c[0]++;
        if(c[a[0]]!=0)c[0]++;
    }
}
inline void cheng(int a[],int i)
{
    int x=0,j;
    for(j=1;j<=a[0];j++)
    {
        a[j]=a[j]*i+x;
        x=a[j]/10;
        a[j]%=10;
    }
    a[j]=x;
    while(a[j]>9)
    {
        a[j+1]=a[j]/10;
        a[j]%=10;
        j++;
    }
    while(a[j]==0&&j>1)
        j--;
    a[0]=j;
}
int main()
{
    scanf("%d %d",&n,&m);
//    cout<<dc(n)<<endl;
//    long long tans=ceil((double)(dc(n)*dc(n+1)*dc(n+3))/(dc(n-1)*dc(n-m+3)));
//    tans+=ceil((double)(dc(n+1)*dc(n+2)*2*m)/(dc(n-m+3)));
    ans1[0]=ans2[0]=ans1[1]=ans2[1]=1;
    for(rint i=1;i<=n;++i)cheng(ans1,i);
    cheng(ans1,n);cheng(ans1,n+1);
    for(rint i=n-m+4;i<=n+3;++i)cheng(ans1,i);
    cheng(ans2,2);cheng(ans2,m);
    for(rint i=1;i<=n+1;++i)cheng(ans2,i);
    for(rint i=n-m+4;i<=n+2;++i)cheng(ans2,i);
    add(ans1,ans2);
    while(c[c[0]]==0 && c[0]>1)c[0]--;
    for(rint i=c[0];i>=1;--i)
        printf("%d",c[i]);
    cout<<endl;
    return 0;
}

>v<

「题解」：[组合数学]：排队

相关推荐