原题传送门
毒瘤计数题
我们设(dp_i)表示至少有(i)个极大数字的概率，(ans_i)表示恰好有(i)个极大数的概率，(mi=Min(n,m,l))
易知：
$$dp_i=sum_{j=i}^{mi} ans_j binom{j}{i}$$
由二项式反演得：
$$ans_i=sum_{j=i}^{mi} dp_j binom{j}{i} (-1)^{j-i}$$
我就不在此证明（实际是我不会证明）
所以我们只需要快速求出dp数组，就珂以快速得到答案
我们需要利用以下结论：
1.我们会发现当((x_0,y_0,z_0))是极大值点时，(x=x_0,y=y_0,z=z_0)三个平面上不珂能再有极大值点且都填上小于((x_0,y_0,z_0))的值，剩下的就像是一个((n-1)(m-1)(l-1))的子问题
2.我们所填的数值是离散化后相对的数值，也就是说，只要选出的数离散化后满足某关系，就是一种合法的状态
设(g_i)表示选定了(i)个极大值点后影响到的平面的交集的方块数，由结论2可知这时候贡献要乘上( binom{N}{g_i}(N=nml))（下文(N)与此时的(N)同义）
易知(g_i=N-(n-i)(m-i)(l-i))
设(f_i)表示选定(i)个极大值点的方案数，易知：
$$f_i=prod_{j=0}^{i-1}(n-j)(m-j)(l-j)$$
设(h_i)表示填充选定了(i)个极大值点后影响到的平面的交集的方案数，易知：
$$
egin{align}
h_i
& = frac{(g_i-1)!}{g_{i-1}!} imes h_{i-1}
& = prod_{j=0}^{i-1} frac{(g_{j+1}-1)!}{g_j!}
end{align}
[
#### 我们这是就珂以求出$dp_i imes N!$了，即至少有$i$个极大数字的种类数，那么$dp_i$也就珂以求出
#### ]
egin{align}
dp_iN!
& = binom{N}{g_i} f_i h_i (N-g_i)!
& = frac{N!}{g_i!(N-g_i)!}f_i prod_{j=0}^{i-1} frac{(g_{j+1}-1)!}{g_j!} (N-g_i)!
& = N! f_i prod_{j=1}^i(g_j-1)!prod_{j=0}^ifrac{1}{g_j!}
& = N! f_i prod_{j=1}^ifrac{1}{g_j}
end{align*}
[
#### $$dp_i=f_i prod_{j=1}^ifrac{1}{g_j}]
这样我们就能快速求出答案了，复杂度为(O(T Min(n_i,m_i,l_i)))
#include <bits/stdc++.h>
#define N 5000005
#define mod 998244353
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Min(register int a,register int b)
{
return a<b?a:b;
}
inline int fastpow(register int a,register int b)
{
int res=1;
while(b)
{
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int T,n,m,l,k,mi,ans;
int fac[N],invf[N];
int f[N],g[N],invg[N],dp[N];
inline int C(register int m,register int n)
{
return 1ll*fac[m]*invf[n]%mod*invf[m-n]%mod;
}
int main()
{
fac[0]=1;
for(register int i=1;i<N;++i)
fac[i]=1ll*fac[i-1]*i%mod;
invf[N-1]=fastpow(fac[N-1],mod-2);
for(register int i=N-1;i;--i)
invf[i-1]=1ll*invf[i]*i%mod;
T=read();
while(T--)
{
n=read(),m=read(),l=read(),k=read();
mi=Min(n,Min(m,l));
if(k>mi)
{
puts("0");
continue;
}
f[0]=1;
for(register int i=0;i<mi;++i)
{
g[i]=1ll*(n-i)*(m-i)%mod*(l-i)%mod;
f[i+1]=1ll*f[i]*g[i]%mod;
}
int fg=1,tot=g[0];
g[mi]=0;
for(register int i=1;i<=mi;++i)
{
g[i]=(0ll+tot+mod-g[i])%mod;
fg=1ll*fg*g[i]%mod;
}
invg[mi]=fastpow(fg,mod-2);
for(register int i=mi;i;--i)
invg[i-1]=1ll*invg[i]*g[i]%mod;
for(register int i=1;i<=mi;++i)
dp[i]=1ll*f[i]*invg[i]%mod;
ans=0;
for(register int i=k;i<=mi;++i)
if((i-k)&1)
ans=(0ll+ans+mod-1ll*C(i,k)*dp[i]%mod)%mod;
else
ans=(0ll+ans+1ll*C(i,k)*dp[i]%mod)%mod;
write(ans),puts("");
}
return 0;
}