【BZOJ2729】[HNOI2012]排队 组合数
组合 排队
2023-09-11 14:15:27 时间
【BZOJ2729】[HNOI2012]排队
Description
某中学有 n 名男同学,m 名女同学和两名老师要排队参加体检。他们排成一条直线,并且任意两名女同学不能相邻,两名老师也不能相邻,那么一共有多少种排法呢?(注意:任意两个人都是不同的)
Input
只有一行且为用空格隔开的两个非负整数 n 和 m,其含义如上所述。
对于 30%的数据 n≤100,m≤100
对于 100%的数据 n≤2000,m≤2000
Output
输出文件 output.txt 仅包含一个非负整数,表示不同的排法个数。注意答案可能很大。
Sample Input
1 1
Sample Output
12
题解:先将老师与男生放到一起,然后将女生插到男生中间,方案书就是A(n+2,n+2)*A(n+3,m),再将老师相邻的方案减去,即将两个老师捆在一起,方案数为A(2,2)*A(n+1,n+1)*A(n+2,m)。
然后就是丧心病狂的高精度时间了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; struct cbig { int len; int v[200000]; cbig(){len=0,memset(v,0,sizeof(v));} cbig(int x) { len=0,memset(v,0,sizeof(v)); while(x) v[++len]=x%10,x/=10; } void operator *= (int b) { int i; for(i=1;i<=len;i++) v[i]*=b; for(i=1;i<=len;i++) v[i+1]+=v[i]/10,v[i]%=10; while(v[len+1]) len++,v[len+1]+=v[len]/10,v[len]%=10; } void operator -= (cbig b) { int i; for(i=1;i<=b.len;i++) v[i]-=b.v[i]; for(i=1;i<=len;i++) { if(v[i]<0) v[i+1]+=v[i]/10,v[i]%=10; if(v[i]<0) v[i+1]--,v[i]+=10; } while(len&&!v[len]) len--; } }ans1,ans2; void A(cbig &ret,int a,int b) { for(int i=a-b+1;i<=a;i++) ret*=i; } int main() { int i,n,m; scanf("%d%d",&n,&m); ans1=cbig(1),A(ans1,n+2,n+2),A(ans1,n+3,m); ans2=cbig(2),A(ans2,n+1,n+1),A(ans2,n+2,m); ans1-=ans2; if(!ans1.len) printf("0"); else for(i=ans1.len;i;i--) printf("%d",ans1.v[i]); return 0; }
相关文章
- Scalaz(14)- Monad:函数组合-Kleisli to Reader
- SQK Server实现 LeetCode 175 组合两个表
- 【设计模式】组合实体模式
- MATLAB中常用的排列、组合、阶乘函数
- 77. 组合
- 踩坑 - markdown 文字字体、大小、 颜色、 高亮、底色样式设置及跨行表格组合
- LCP 18. 早餐组合
- 【Kotlin 协程】协程启动 ③ ( 协程组合并发 | 挂起函数串行执行 | 协程组合并发执行挂起函数 )
- Java 实现组合(Composite)模式
- 小学生蓝桥杯Python闯关 | 三位数奇数组合
- 设计模式之组合模式
- HDLBits练习汇总-08-组合逻辑设计测试--加法器电路
- UML图讲解(关联关系,单向关联,双向关联,自关联,组合关系,依赖关系,继承关系,实现关系)
- 经典方法实现投资组合优化【Matlab实现】
- 数学知识——求组合数
- 【C++要笑着学】继承 | 子类默认成员函数 | 单继承与多继承 | 钻石继承 | 虚拟继承 | 继承和组合