洛谷P4640 王之财宝 [BJWC2008] 数论

佚名 7年前 (2019-04-13) 随笔 1348人围观抢沙发百度已收录

正解:容斥+Lucas+组合数学

解题报告:

传送门!

和上一篇题解的题差不多,,,双倍经验趴大概算

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

还是说下还是有点儿区别的来着$QwQ$

两个小差别分别港下$QwQ$

首先有$m-n$件是无穷个的,,,$so$在ans的求值的时候本来是$\binom{n-1}{n+s-1}$来着,显然就要变成$\binom{m-1}{m+s-1}$

啊对了说下,因为这题代码我是直接由上题的代码魔改来的,,,$so$命名和题目不太一样,,,我这儿的按读入顺序排是,$m,n,s,mod$

然后还一个是说只用选不超过$s$件,这个可以理解为另外添了一个物品,有无数个,这样就可以当做是$s$件来做辣,少的就当全用这个新增的填上了就欧克了

还有一个小细节,,,因为和解法没什么关系只是优化复杂度的,,,就这题里的mod范围是<=1e5,$so$可以预处理一下组合数,否则就会获得$TLE$的好成绩,,,(为什么上一题不用预处理呢,一个是上一题的mod是1e9开不下,另一个是上一题是和$n$有关,$n$的范围在20以内就很欧克$QwQ$,这题里是和$m$有关就不太欧克了$QAQ$

$over!$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define int long long
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=20+10,M=1e5+10;
int tot,poww[N]={1},m,n,s,mod,f[N],as,jc[M],inv[M];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il int power(ri x,ri y){ri ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;}
il void pre(ri x)
{
    jc[0]=1;rp(i,1,x)jc[i]=1ll*jc[i-1]*i%mod;
    inv[x]=power(jc[x],mod-2);my(i,x-1,0)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
il int C(ri x,ri y){if(x<0 || y<0 || x<y)return 0;return 1ll*jc[x]*inv[y]%mod*inv[x-y]%mod;}
int lucas(ri x,ri y){if(!x && !y)return 1;return 1ll*C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;}
il void cal(ri zt)
{
    ri del=1,cnt=s;
    rp(i,0,n-1)if(zt&(poww[i])){del=-del,cnt-=f[i+1]+1;if(cnt<0)return;}
    as=(as+1ll*lucas(cnt+m-1,m-1)*del%mod+mod)%mod;
}

signed main()
{
//    freopen("4640.in","r",stdin);freopen("4640.out","w",stdout);
    m=read()+1;n=read();s=read();mod=read();rp(i,1,n)poww[i]=poww[i-1]<<1,f[i]=read();pre(mod-1);
    rp(i,0,poww[n]-1)cal(i);printf("%lld\n",as);
    return 0;
}