[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 字符串查找