Luogu5400 CTS2019 random cube (inclusion exclusion principle)

Considering the tolerance and exclusion, the probability of at least k maxima is calculated. Let's suppose that the lattice corresponding to these K numbers is (k,k,k) (1,1,1). Then a lattice with one-dimensional coordinate less than or equal to K will have an impact on whether these lattices will become maxima. First, all such lattices are mapped to a set of numbers, that is, the answer is multiplied by a combination number. Then we need to consider how many kinds of legal order these lattices have.

This arrangement needs to satisfy that (i,i,i) can not appear a lattice with one-dimensional coordinate i before. It can be seen that after filling in (i,i,i), the grid with the minimum value of i in all three-dimensional coordinates can be filled. The number of such lattices is easy to calculate. So we consider putting the lattices into the permutation one by one. Obviously, the first place can only be put (k,k,k). Then all the lattices with the minimum value of three-dimensional coordinates of K are unlocked. We use a combination number to put them anywhere in the permutation, and then continue to put them (k-1,k-1,k-1), and so on.

In this way, we can get some things from the final generalization, and we can find that what we want to calculate is the inverse element of an array prefix product. We can use classic trick to find out the inverse element of the whole array product and then restore it in reverse order, which can achieve linearity.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 998244353
#define N 5000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int T,n,m,l,k,fac[N],inv[N],f[N],g[N];
int ksm(int a,int k)
{
    int s=1;
    for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
    return s;
}
int Inv(int a){return ksm(a,P-2);}
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
int A(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[n-m]%P;}
int min(int x,int y,int z){return min(min(x,y),z);}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    const char LL[]="%I64d\n";
#else
    const char LL[]="%lld\n";
#endif
    T=read();
    fac[0]=1;for (int i=1;i<=N-10;i++) fac[i]=1ll*fac[i-1]*i%P;
    inv[0]=inv[1]=1;for (int i=2;i<=N-10;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
    for (int i=2;i<=N-10;i++) inv[i]=1ll*inv[i]*inv[i-1]%P;
    while (T--)
    {
        n=read(),m=read(),l=read(),k=read();
        int ans=0;
        for (int i=1;i<=min(n,m,l);i++) f[i]=(1ll*(n-i+1)*(m-i+1)%P*(l-i+1)%P-1ll*(n-i)*(m-i)%P*(l-i)%P+P)%P;
        for (int i=1;i<=min(n,m,l);i++) f[i]=(f[i]+f[i-1])%P;g[min(n,m,l)]=1;
        for (int i=1;i<=min(n,m,l);i++) g[min(n,m,l)]=1ll*g[min(n,m,l)]*f[i]%P;
        g[min(n,m,l)]=Inv(g[min(n,m,l)]);
        for (int i=min(n,m,l)-1;i>=1;i--) g[i]=1ll*g[i+1]*f[i+1]%P;
        for (int i=k;i<=min(n,m,l);i++)
        {
            int waytochoosemax=1ll*A(n,i)*A(m,i)%P*A(l,i)%P;
            if (i-k&1) inc(ans,P-1ll*C(i,k)*waytochoosemax%P*g[i]%P);
            else inc(ans,1ll*C(i,k)*waytochoosemax%P*g[i]%P);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Tags: Python less

Posted on Sun, 03 Nov 2019 14:38:48 -0800 by kellydigital