【BZOJ 1272】 [BeiJingWc2008]Gate Of Babylon

1272: [BeiJingWc2008]Gate Of BabylonTime Limit:10 SecMemory Limit:162 MBSubmit:197Solved:92[Submit][Status][Discuss]Description

Input

Output

Sample Input

Sample Output

12

HINT

容斥原理+多重集的组合数+lucas定理

1.首先，看到有限制的只有15个，因此可以用容斥原理：

ans=全部没有限制的方案-有一个超过限制的方案数+有两个超过限制的方案数-有三个超过限制的方案数….

2.多重集的组合数：

把n组无限制的数中选m个的方案数：C(n+m-1,n)。

证明：

xi为选xi个第i组数，这个问题相当于求x1+x2+x3+..+xm=n，求x解集的方案数，也就是有n个1，用m-1个0将他们分隔开的方案数，也就是C(n+m-1,m)

有一个超过限制直接用总数减去（这个的限制+1)就是当前的总数，相当于强制要选限制+1个，，其他任意。。。

注意本题是要求不超过m的方案数，也就是C(n+0-1,0)+C(n+1-1,1)+C(n+2-1,2)+…+C(n+m-1,m)=C(n+m,m)

(因为C(n,m)=C(n-1,m-1)+C(n-1,m))

3.最后由于M，N太大，不能直接算组合数，所以用lucas定理来求。详见【HDU 3037】

#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <cstdio>#define LL long long#define M 100005using namespace std;int n,m,mod,k,b[20];LL inv[M],fac[M],ans=0;LL Pow(LL x,LL n){LL base=x,ans=1;while (n){if (n&1) ans=ans*base%mod;base=base*base%mod;n>>=1;}return ans;}void Prepare(){fac[0]=1;for (int i=1;i<=mod;i++)fac[i]=fac[i-1]*i%mod;inv[mod-1]=Pow(mod-1,mod-2);inv[0]=1;for (int i=mod-2;i;i–)inv[i]=inv[i+1]*(i+1)%mod;}LL C(LL n,LL m){if (n<m) return 0;if (n<mod&&m<mod)return fac[n]*inv[m]%mod*inv[n-m]%mod;return C(n%mod,m%mod)*C(n/mod,m/mod)%mod;}void RC(int now,int x,int w){if (now==k+1){ans=(ans+x*C(m+n-w,m-w))%mod;return;}RC(now+1,-x,w+b[now]+1);RC(now+1,x,w);}int main(){scanf("%d%d%d%d",&n,&k,&m,&mod);for (int i=1;i<=k;i++)scanf("%d",&b[i]);Prepare();RC(1,1,0);printf("%lld\n",(ans%mod+mod)%mod);return 0;}

因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。