题解 | #[HNOI2012]排队#

站队问题，插空法的变形

1.首先，如果只有两种人的话我们直接使用插空法就好了
对于n个男生和m个女生，如果要求女生之间不站在一起，首先让男生任意排列，在每个男生之间的空位(加上开头和结尾)一共n+1个位置中任意选取m个位置来让女生站队，最后在对女生进行任意排列

即，公式如下： $A_{n}^{n} \times C_{n+1}^{m} \times A_{m}^{m}$

2.下面我们来看本题，多出来一个老师这个群体，要求是老师也不能相邻，因此我们需要想如何把三种群体转换为两种群体

思路来了：符合要求排列数==老师任意排列数-老师相邻排列数

我们应当将老师看作男同学的一种，不考虑老师本身个体的的差异化。带入上述公式符合要求排列数==老师任意排列数-老师相邻排列数

老师任意排列的数量： $A_{n+2}^{n+2} \times C_{n+3}^{m} \times A_{m}^{m}$

老师相邻排列数（将老师们用绳子捆成一捆，看作一位男同学，这样子就能保证相邻了，只不过要注意捆在一起也有顺序，要×2）：

$A_{2}^{2} \times A_{n+1}^{n+1} \times C_{n+2}^{m} \times A_{m}^{m}$

因此答案的数量为 $A_{n+2}^{n+2} \times C_{n+3}^{m} \times A_{m}^{m} -A_{2}^{2} \times A_{n+1}^{n+1} \times C_{n+2}^{m} \times A_{m}^{m}$

化简一下，用循环可以求解的形式表达出来就是 $(n^{2}+3n+2m)\times (n+1)! \times \prod_{n+4-m}^{n+2}i$

注意！！别忘记写高精度！！！！

下面奉上代码:

//万能头文件
#include<bits/stdc++.h>
using namespace std;

int ans[MAXN]={0};
int cnt=1;
//高精度乘法
void multi(int x){
    for(int i=1;i<=cnt;i++){ 
        ans[i]=x; 
    } 
    //进位 
    for(int i=1;i=10){
        ans[cnt+1]+=ans[cnt]/10,ans[cnt]%=10;
    cnt++;
    }
}

int n,m;
//所有乘法操作
void op(){
    multi(n*n+3n+2m);
    for(int i=1;i<=n+1;i++) 
        multi(i); 
    for(int i=n+4-m;i<=n+2;i++) 
        multi(i); 
} 

int main(){ 
    memset(ans,0,sizeof(ans)); 
    ans[1]=1; 
    scanf("%d %d",&n,&m); 
    op(); 
    //输出 
    for(int i=cnt;i>=1;i--){
    printf("%d",ans[i]);
    }
    return 0;
}