正解:$exLucas$+容斥

解题报告:

传送门!

在做了一定的容斥的题之后再看到这种题自然而然就应该想到容斥,,,?

没错这题确实就是容斥,和这题有点儿像

注意下的是这里的大于和小于条件处理方式不同昂$QwQ$

对于大于等于,直接在一开始就先给它那么多就好,就先提前把$m-=\sum_{i=n_{1}+1}^{n_{1}+n_{2}} A_i$,这样就只剩小于等于的条件了

小于等于,一看最多就8个,显然就成了经典容斥套路题了鸭,

于是就枚举哪个爆了,然后可重排列搞下,容斥下,就做完了

放下推出来的式子趴,,,$\sum_{s} [\ |s|\ \&\ 1\ ]\cdot \binom{n-\sum_{i\in S}(x_{i}+1)+m-1}{m}$,大概是这样儿的,如果有问题我打完代码之后会$upd$的$QwQ$

但是还有一个要注意的就,这个$mod$不一定是质数昂,,,所以考虑用个$exLucas$就欧克了鸭

$over$

昂还有一个卡时间的小$tip$,,,就是在$exLucas$里最开始特判下,当$n<0$,$m<0$,$n<m$的时候就可以直接$return\ 0$了,这样就能成功从2571$ms$变成150$ms$,,,

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#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)

const int N=1e6+;

int fac_cnt,A[N],B[N],mod,wei[N],tmpp;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ex_gcd(ri a,ri b,ri &x,ri &y){if(!b){x=;y=;return;}ex_gcd(b,a%b,y,x);y-=(a/b)*x;}

il int power(ri x,ri y){/*if(!x)return 0;*/ri ret=;while(y){if(y&)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=;}return ret;}

struct nod

{

    int p,pk,jc[N];

    il void init(){jc[]=;rp(i,,pk)jc[i]=1ll*jc[i-]*(i%p?i:)%pk;}

    il int power(ri x,ri y){ri ret=;while(y){if(y&)ret=1ll*ret*x%pk;x=1ll*x*x%pk;y>>=;}return ret;}

    il int inv(ri d){ri x,y;ex_gcd(d,pk,x,y);return (x%pk+pk)%pk;}

    il int multi(ri x){ri ret=;while(x){ret=ret*power(jc[pk],x/pk)%pk*jc[x%pk]%pk;x/=p;}return ret;}

    il void getp(ri x,ri op,ri &k){while(x)k+=op*(x/p),x/=p;}

    il int C(ri n,ri m)

        {

            ri a=multi(n),b=multi(m),c=multi(n-m),k=;getp(n,,k);getp(m,-,k);getp(n-m,-,k);

            return 1ll*a*inv(b)%pk*inv(c)%pk*power(p,k)%pk;

        }

    nod(){pk=;}

}fac[];

il int crt()

{

    ri p=A[],r=B[];

    rp(i,,fac_cnt)

    {ri x,y,np=A[i]*p;ex_gcd(p,A[i],x,y);x=(1ll*x*(B[i]-r)%np+np)%np;r=(1ll*x*p%np+r+np)%np;p=np;}

    return r;

}

il int ex_lucas(ri n,ri m)

{

    if(n< || m< || n<m)return ;

    rp(i,,fac_cnt)A[i]=fac[i].pk,B[i]=fac[i].C(n,m);

    return crt();

}

main()

{

    int T=read();tmpp=mod=read();

    for(ri i=;i*i<=mod;++i){if(!(mod%i))fac[++fac_cnt].p=i;while(!(mod%i))fac[fac_cnt].pk*=i,mod/=i;}

    if(mod>)fac[++fac_cnt].p=mod,fac[fac_cnt].pk=mod;mod=tmpp;

    rp(i,,fac_cnt)fac[i].init();

    while(T--)

    {

        ri n=read(),n1=read(),n2=read(),m=read()-n,S=<<n1,as=;

        rp(i,,n1+n2)wei[i]=read()-;rp(i,n1+,n1+n2)m-=wei[i];

        rp(i,,S-)

        {

            ri opt=,tmp_m=m;

            rp(j,,n1)if(i&(<<(j-)))opt=mod-opt,tmp_m-=wei[j]+;

            as=(as+1ll*opt*ex_lucas(tmp_m+n-,n-)%mod)%mod;

        }

        printf("%lld\n",as);

    }

    return ;

}

巴特西

洛谷$P$3301 $[SDOI2013]$方程 $exLucas$+容斥

正解:$exLucas$+容斥

解题报告:

最新文章

热门文章