【BZOJ】【1272】【BeiJingWC2008】Gate of Babylon

2023-03-20 12:01:09

组合数学+容斥原理

　　多重集组合数0.0还带个数限制？ ——> 《组合数学》第6章 6.2带重复的组合

　　组合数还要模P 0.0？ ——> Lucas定理

　　啊……要算组合数啊……除以阶乘神马的太麻烦肿么办？还要模P……没关系~我们可以搞预处理啊= =预处理粗来【阶乘%P】和【阶乘在模P意义下的逆元】

 void calc(){

     fac[]=;

     F(i,,P-) fac[i]=fac[i-]*i%P;

     inv[P-]=pow(fac[P-],P-); inv[]=;

     D(i,P-,) inv[i]=inv[i+]*(i+)%P;

 }

预处理

　　然后容斥么……反正只有15种暴力容斥搞搞就好了……就是枚举么……dfs一下

 /**************************************************************

     Problem: 1272

     User: Tunix

     Language: C++

     Result: Accepted

     Time:96 ms

     Memory:2840 kb

 ****************************************************************/

 //BZOJ 1272

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 /*******************tamplate********************/

 typedef long long LL;

 const int N=;

 LL n,T,m,P,ans,fac[N],inv[N];

 int b[];

 LL pow(LL a,LL b){

     LL r=,base=a;

     for(;b;b>>=,base=base*base%P)

         if (b&) r=r*base%P;

     return r;

 }

 inline LL c(LL n,LL m){

     if (n<m) return ;

     if (n<P && m<P) return fac[n]*inv[m]%P*inv[n-m]%P;

     return c(n%P,m%P)*c(n/P,m/P)%P;

 }

 void calc(){

     fac[]=;

     F(i,,P-) fac[i]=fac[i-]*i%P;

     inv[P-]=pow(fac[P-],P-); inv[]=;

     D(i,P-,) inv[i]=inv[i+]*(i+)%P;

 }

 void dfs(int x,int w1,LL w2){

     if (x==T+){

         ans=(ans + w1*(c(m+n-w2,n)-c(n-w2-,n)))%P;

         return;

     }

     dfs(x+,-w1,w2+b[x]+);

     dfs(x+,w1,w2);

 }

 int main(){

 //  freopen("input.txt","r",stdin);

     n=getint(); T=getint(); m=getint(); P=getint();

     F(i,,T) b[i]=getint();

     calc();

     dfs(,,);

     printf("%lld\n",(ans+P)%P);

     return ;

 }