[CTS2019]随机立方体（容斥+组合数学）

这题七次方做法显然，但由于我太菜了，想了一会发现也就只会这么多，而且别的毫无头绪。发现直接做不行，那么，容斥！

f[i]为至少i个极值的方案，然后这里需要一些辅助变量，a[i]表示选出i个三维坐标均不相同的i个极大值的方案数，g[i]表示i个极大的数任意一个至少有一维坐标相同的点的个数，h[i]表示g[i]的极值可以同时存在的方案数，那么有f[i]=C(nml,g[i])a[i]h[i](nml-g[i])!。

a[i]很容易求得，就是(∏(n-j)(m-j)(l-j))/i!，其中j∈[0,i)，g[i]更好求，就是nml-(n-i)(m-i)(l-i)

然后要进行一些关于上升幂的运算，我这里打不出式子（因为太菜了不会LaTeX），所以就不打了。注意维护g[i]的前缀积，具体细节看code吧。

#include<bits/stdc++.h>

using namespace std;

const int N=5e6+,mod=;

int n,m,l,k,mn,ans,fac[N],inv[N],a[N],f[N],g[N],h[N],pre[N];

int calc(int x){return 1ll*(n-x)*(m-x)%mod*(l-x)%mod;}

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

int C(int a,int b){return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}

int main()

{

    inv[]=inv[]=fac[]=;for(int i=;i<N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    for(int i=;i<N;i++)fac[i]=1ll*fac[i-]*i%mod,inv[i]=1ll*inv[i-]*inv[i]%mod;

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d%d",&n,&m,&l,&k);

        mn=min(n,min(m,l));

        a[]=h[]=pre[]=;

        for(int i=;i<=mn;i++)a[i]=1ll*a[i-]*calc(i-)%mod;

        for(int i=;i<=mn;i++)g[i]=(1ll*g[i-]+calc(i-)-calc(i)+mod)%mod;

        for(int i=;i<=mn;i++)pre[i]=1ll*pre[i-]*g[i]%mod;

        pre[mn]=qpow(pre[mn],mod-);

        for(int i=mn;i;i--)pre[i-]=1ll*pre[i]*g[i]%mod;

        for(int i=;i<=mn;i++)f[i]=1ll*a[i]*pre[i]%mod;

        ans=;

        for(int i=k;i<=mn;i++)

        if((i-k)&)ans=(ans-1ll*C(i,k)*f[i]%mod+mod)%mod;

        else ans=(ans+1ll*C(i,k)*f[i])%mod;

        printf("%d\n",ans);

    }

}

巴特西

[CTS2019]随机立方体（容斥+组合数学）

最新文章

热门文章