P5400 [CTS2019] 随机立方体 题解

题目链接

点击打开链接

题目解法

参考 cmd 的博客

好复杂的推式子题，而且三维的对我来说好难想象/ll

首先二项式反演，把恰好 \(k\) 个变成求至少 \(i\) 个的方案数
令极大格子有至少 \(i\) 个的方案数为 \(f_i\)，\(R=\min\{n,m,k\}\)
特判掉 \(k>R\) 答案为 \(0\)
根据二项式反演，答案为 \(\sum\limits_{i=k}^R f_i\binom{i}{k}(-1)^{i-k}\)

现在需要快速算出 \(\forall_{i=1}^R f_i\)
咋算？
令 \(g_x=(n-x)(m-x)(l-x),\;G_x=nml-g_x\)
考虑钦定 \(i\) 个极大格子，则有 \(g_i\) 个格子不受限
先考虑把这些不受限的格子给排好，首先在 \(nmk\) 个数中选出 \(g_i\) 个数，然后将这些数任意排列，所以方案数显然为 \(\binom{nml}{G_i}g_i!\)
再考虑受限的位置的选择，不难得到方案数为 \(\prod\limits_{j=1}^i(n-j)(m-j)(l-j)\)，但这样钦定了顺序，所以要 \(\times \frac{1}{i!}\)

现在考虑最难的情况：有 \(i\) 个无序格子钦定是极大的，求和这 \(i\) 个格子牵连的 \(G_i\) 个格子合法排列的方案数
有些格子会被多个极大格限制，考虑如何使每个格子只被 \(1\) 个极大格限制
我们将极大格的值按照从小到大排列，分别是从外到里的每一层
这时我们惊奇地发现每个格子只被当前这一圈的极大格限制，这样就好做多了
说明需要借用一下 cmd 的图：点击打开图片
考虑从里往外排列每一个极大格，同时这个极大格限制的一圈格子都需要被排列
假设当前在考虑第 \(j\) 层，考虑之前的格子已经被扣掉了，现在只剩下 \(G_j\) 个位置，因为当前层的极大值一定是最大数，所以只要排列剩下的 \(g_{j-1}-g_{j}-1\) 个格子就可以了，所以方案数为 \(\prod\limits_{j=1}^i(G_j-1)^{\underline{g_{j-1}-g_{j}-1}}=\prod\limits_{j=1}^i\frac{(G_j-1)!}{(G_j-g_{j-1}+g_j+1)!}=\prod\limits_{j=1}^i\frac{(G_j-1)!}{G_{j-1}!}\)
因为极大格之间是无序的，我们只是人为钦定了顺序，所以方案数需要 \(\times i!\)

整理一下，\(f_i=\binom{nml}{G_i}g_i!\times \frac{1}{i!}\prod\limits_{j=1}^ig_j\times i!\prod\limits_{j=1}^i\frac{(G_j-1)!}{G_{j-1}!}\\ =(nml)!\frac{1}{G_i!}\times \prod\limits_{j=1}^ig_j\times \prod\limits_{j=1}^i\frac{(G_j-1)!}{G_{j-1}!}\)
因为最后要求概率，所以要除以 \((nml)!\)
所以 \(ans=\frac{1}{G_i!}\times \prod\limits_{j=1}^ig_j\times \prod\limits_{j=1}^i\frac{(G_j-1)!}{G_{j-1}!}\)
还是不太好做，考虑进一步化简
把 \(\frac{1}{G_i!}\) 放到 \(\prod\limits_{j=1}^i\frac{(G_j-1)!}{G_{j-1}!}\) 里面
所以 \(ans=\prod\limits_{j=1}^ig_j\frac{1}{G_0}\prod\limits_{j=1}^i\frac{(G_j-1)!}{G_j!}\\ =\prod\limits_{j=1}^ig_j\prod\limits_{j=1}^i\frac{1}{G_j}\)

求 \(\frac{1}{G_x}\) 可以通过线性求逆元的方法求
时间复杂度 \(O(T\min\{n,m,k\})\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=5000010,P=998244353;
int fac[N],ifac[N];
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
    return res;
}
void init(int n){
    fac[0]=1;
    F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qmi(fac[n],P-2);
    DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
int binom(int x,int y){ return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;}
int f[N],g[N],G[N];
void work(){
    int n=read(),m=read(),l=read(),k=read();
    int R=min(min(n,m),l);
    if(k>R){ puts("0");return;}
    int tot=1ll*n*m%P*l%P;
    G[0]=1;
    F(i,0,R){
        g[i]=1ll*(n-i)*(m-i)%P*(l-i)%P;
        if(i) G[i]=1ll*G[i-1]*(tot-g[i]+P)%P;
    }
    G[R]=qmi(G[R],P-2);
    DF(i,R-1,0) G[i]=1ll*G[i+1]*(tot-g[i+1]+P)%P;
    int mul=1;
    F(i,1,R) G[i]=1ll*G[i]*mul%P,mul=1ll*mul*(tot-g[i]+P)%P;
    f[0]=1;
    F(i,1,R) f[i]=1ll*f[i-1]*g[i-1]%P*G[i]%P;
    int ans=0;
    F(i,k,R){
        if((k-i)&1) ans=(ans-1ll*f[i]*binom(i,k)%P+P)%P;
        else ans=(ans+1ll*f[i]*binom(i,k))%P;
    }
    printf("%d\n",ans);
}
int main(){
    init(N-1);
    int T=read();
    while(T--) work();
    return 0;
}