[BZOJ2729][HNOI2012]排队（组合数学+高精度）

2019-11-08 18:35:11

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

各种分类讨论狗屎题先任务两个人相同，最后再乘全排先放好个女生（m+1个空），然后将老师插进去（m+3个空），再将男生插进去

两个老师相邻放在女生中间m-1种，有m-1个空必须放男生，其余随意放在女生旁边2种，有m个空必须放男生，其余随意两个老师不相邻都放在女生中间C2m−1 $C_{m-1}^2$ 种，有m-3个空必须放男生，其余随意都放在女生旁边1种，有m-1个空必须放男生，其余随意一个中间一个旁边2*(m-1)种，有m-2个空必须放男生，其余随意

两个模型 1.n个球，放在m个盒子里，k个盒子必须放先将k个球放在k个盒子里，剩n-k个球，再随意放在m个盒子里 2.n个球，放在m个盒子里，盒子允许为空插板法 Cm−1n+m−1 $C_{n+m-1}^{m-1}$

每一次算组合数，质因数分解然后写一个高精乘单精就行了果然什么东西一扯上高精就恶心了…

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int n,m;int PRime[350],p[2010],cnt[350],num[2010];struct data{int a[5005];};data one,zero,now,ans;void get_p(){ for (int i=2;i<=2005;++i) { if (!p[i]) prime[++prime[0]]=i,num[i]=prime[0]; for (int j=1;j<=prime[0]&&i*prime[j]<=2005;++j) { p[i*prime[j]]=1; if (i%prime[j]==0) break; } }}data jia(data a,data b){ data ans=zero; int len=max(a.a[0],b.a[0]); for (int i=1;i<=len;++i) ans.a[i]=a.a[i]+b.a[i]; for (int i=1;i<=len;++i) { ans.a[i+1]+=ans.a[i]/1000; ans.a[i]%=1000; } if (ans.a[len+1]) ++len; ans.a[0]=len; return ans;}data cheng(data a,int b){ data ans=zero; int len=a.a[0]; for (int i=1;i<=len;++i) ans.a[i]=a.a[i]*b; for (int i=1;i<=len;++i) { ans.a[i+1]+=ans.a[i]/1000; ans.a[i]%=1000; } while (ans.a[len+1]) { ++len; ans.a[len+1]+=ans.a[len]/1000; ans.a[len]%=1000; } while (len>1&&!ans.a[len]) --len; ans.a[0]=len; return ans;}void calc(int x,int add){ for (int i=2;x>1&&i*i<=x;++i) while (x%i==0) cnt[num[i]]+=add,x/=i; if (x>1) cnt[num[x]]+=add;}data C(int n,int m){ if (n<0||m<0||m>n) return zero; memset(cnt,0,sizeof(cnt)); data ans=one; for (int i=n-m+1;i<=n;++i) calc(i,1); for (int i=1;i<=m;++i) calc(i,-1); for (int i=1;i<=prime[0];++i) { while (cnt[i]>0) { ans=cheng(ans,prime[i]); --cnt[i]; } } return ans;}data choose(int n,int m,int k){ if (n<k) return zero; data ans=C(n-k+m-1,m-1); return ans;}void print(data a){ for (int i=a.a[0];i>=1;--i) { if (i==a.a[0]) {printf("%d",a.a[i]);continue;} if (a.a[i]>=100) printf("%d",a.a[i]); else if (a.a[i]>=10) printf("0%d",a.a[i]); else printf("00%d",a.a[i]); } puts("");}int main(){ scanf("%d%d",&n,&m);get_p(); memset(zero.a,0,sizeof(zero.a));zero.a[0]=1; memset(one.a,0,sizeof(one.a));one.a[0]=one.a[1]=1; ans=zero; // 1. 两个老师放在一起 // 1.1 两个老师在里面 now=choose(n,m+3,m-1); now=cheng(now,m-1); ans=jia(ans,now); // 1.2 两个老师在边上 now=choose(n,m+3,m); now=cheng(now,2); ans=jia(ans,now); // 2. 两个老师分开放 // 2.1 两个老师都在里面 now=choose(n,m+3,m-3); now=cheng(now,(m-1)*(m-2)/2); ans=jia(ans,now); // 2.2 两个老师都在边上 now=choose(n,m+3,m-1); ans=jia(ans,now); // 2.3 一个老师在里面一个老师在边上 now=choose(n,m+3,m-2); now=cheng(now,2*(m-1)); ans=jia(ans,now); memset(cnt,0,sizeof(cnt)); for (int i=1;i<=n;++i) calc(i,1); for (int i=1;i<=m;++i) calc(i,1); for (int i=1;i<=2;++i) calc(i,1); for (int i=1;i<=prime[0];++i) while (cnt[i]) { ans=cheng(ans,prime[i]); --cnt[i]; } print(ans);}

上一篇：有符号数和无符号数负数

下一篇：LintCode 13 字符串查找