题解 | #[HNOI2012]排队#
[HNOI2012]排队
https://ac.nowcoder.com/acm/problem/20097
站队问题，插空法的变形
对于n个男生和m个女生，如果要求女生之间不站在一起，首先让男生任意排列，在每个男生之间的空位(加上开头和结尾)一共n+1个位置中任意选取m个位置来让女生站队，最后在对女生进行任意排列
即，公式如下：
2.下面我们来看本题，多出来一个老师这个群体，要求是老师也不能相邻，因此我们需要想如何把三种群体转换为两种群体
思路来了：符合要求排列数==老师任意排列数-老师相邻排列数
我们应当将老师看作男同学的一种，不考虑老师本身个体的的差异化。带入上述公式符合要求排列数==老师任意排列数-老师相邻排列数
老师任意排列的数量：
老师相邻排列数（将老师们用绳子捆成一捆，看作一位男同学，这样子就能保证相邻了，只不过要注意捆在一起也有顺序，要×2）：
因此答案的数量为
化简一下，用循环可以求解的形式表达出来就是%5Ctimes%20(n%2B1)!%20%5Ctimes%20%5Cprod_%7Bn%2B4-m%7D%5E%7Bn%2B2%7Di)
注意！！别忘记写高精度！！！！
注意！！别忘记写高精度！！！！
注意！！别忘记写高精度！！！！
下面奉上代码:
//万能头文件
#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;
} 
投递字节跳动等公司10个岗位 >
