CodeVS1994 排队

2019-11-06 08:24:28

字体：大中小

来源：转载

供稿：网友

链接

　　http://codevs.cn/PRoblem/1994/

题解

　　高中排列组合题　　ans=An+2n+2AmmCmn+3−2An+1n+2Cmn+1 $ans=A_{n+2}^{n+2}A_m^mC_{n+3}^m-2A_{n+2}^{n+1}C_{n+1}^m$ 　　稍微解释一下，就是先把老师看做男生，男生先全排列，然后形成n+3 $n+3$ 个空，女生来插，同样女生也要全排列。　　再捆绑法减去老师相邻的情况。　　然后就可以开始打恶心的高精度了。

代码

//组合数+高精 #include <cstdio>#include <algorithm>#define maxn 2100#define ll long long#define ya 1000000000using namespace std;ll prime[maxn], q[maxn], mark[maxn], N, M, A[maxn], B[maxn];inline void shai(){ ll i, j; for(i=2;i<maxn;i++) { if(!mark[i])prime[++prime[0]]=i; for(j=1;j<=prime[0] and i*prime[j]<maxn;j++) { mark[i*prime[j]]=1; if(i%prime[j]==0)break; } }}inline void mult(ll *num, ll x){ ll i; for(i=1;i<=num[0];i++)num[i]*=x; for(i=1;i<=num[0];i++)num[i+1]+=num[i]/ya, num[i]%=ya; if(num[num[0]+1])num[0]++;}inline void minu(ll *a, ll *b){ ll i; for(i=1;i<=b[0];i++)a[i]-=b[i]; for(i=1;i<=a[0];i++)if(a[i]<0)a[i+1]--,a[i]+=ya; for(;a[a[0]]==0;a[0]--);}inline void show(ll *num){ ll i, j; printf("%lld",num[num[0]]); for(i=num[0]-1;i>0;i--) { for(j=ya/10;j>1;j/=10)if(num[i]<j)putchar(48); printf("%lld",num[i]); }}inline void resolve(ll x, ll d){ ll t, i; for(i=1,t=x;prime[i]<=t;i++) for(;t%prime[i]==0;t/=prime[i])q[i]+=d;}void calc(ll *num){ ll i, j, t; for(i=1;i<=prime[0];i++) { for(j=1,t=1;j<=q[i];j++) { if(t*prime[i]>ya)mult(num,t),t=1; t*=prime[i]; } if(t>1)mult(num,t); }}void solve(){ ll i; if(M>N+3)return; for(i=1;i<=N+2;i++)resolve(i,1); for(i=1;i<=M;i++)resolve(i,1); for(i=N+3;i>=N+3-M+1;i--)resolve(i,1); for(i=1;i<=M;i++)resolve(i,-1); A[0]=A[1]=1;calc(A); for(i=1;i<=prime[0];i++)q[i]=0; resolve(2,1); for(i=1;i<=N+1;i++)resolve(i,1); for(i=1;i<=M;i++)resolve(i,1); for(i=N+2;i>=N+2-M+1;i--)resolve(i,1); for(i=1;i<=M;i++)resolve(i,-1); if(M>N+2)return; B[0]=B[1]=1;calc(B); minu(A,B);}int main(){ shai(); scanf("%lld%lld",&N,&M); solve(); if(N==0)putchar(48); else show(A); return 0;}

上一篇：写代码一定要仔细

下一篇：修改Ubuntu的aptget源为阿里源的方法

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注