Description
Solution
记\(N=min(n,m,l)\)
首先考虑容斥，记\(f(i)\)为至少有i个位置是极大的，显然极大的位置数上界是N。
那么显然\(Ans=\sum\limits_{i=k}^{N}(-1)^{i-k}f(i){i \choose k}\)
现在来计算\(f\)
我们考虑立方体中哪些位置是极大的，显然这些极大的位置三维坐标都互不相同，然后剩下的怎么选概率都是一样的。
将这i个位置按值从小到大排起来，那么有序的选出\(i\)个位置的方案数就是\(n^{i\downarrow}m^{i\downarrow}l^{i\downarrow}\)，下降箭头表示下降幂。
然后这些位置都必须是这些坐标中最大的。记\(S_j\)为与第j个位置有坐标相同的点集。
如果直接对于每一个位置j计算它是\(S_j\)中最大的点的概率，然后再全部乘在一起，这是不正确的，因为\(S\)之间可能有交，即使排除了交的部分，概率仍然是不独立的。
但是我们注意到位置已经按照小到大排了，因此\(a_2>a_1\geq S_1,a_2\geq S_2\)，因此一定满足\(a_2\geq S_1\cup S_2,a_3\geq S_1\cup S_2 \cup S_3......\)
可以发现，这样每个位置是极大的概率就独立了。
因此\(f(k)=n^{k\downarrow}m^{k\downarrow}l^{k\downarrow}\sum\limits_{j=1}^{k}{1\over nml-(n-j)(m-j)(l-j)}\)
预处理n个数的逆元可以用前缀积做到\(O(n+\log)\)，因此总的时间复杂度就是\(O(tN)\)的
Code
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 5000005
#define LL long long
#define mo 998244353
using namespace std;
LL js[N],ny[N],d[N],nd[N],ds[N];
LL ksm(LL k,LL n)
{
LL s=1;
for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;
return s;
}
LL C(int n,int m)
{
if(n<m) return 0;
return js[n]*ny[m]%mo*ny[n-m]%mo;
}
LL n,m,l,r,n1;
int main()
{
int t;
cin>>t;
js[0]=1;
fo(i,1,N-5) js[i]=js[i-1]*(LL)i%mo;
ny[N-5]=ksm(js[N-5],mo-2);
fod(i,N-6,0) ny[i]=ny[i+1]*(LL)(i+1)%mo;
while(t--)
{
cin>>n>>m>>l>>r;
n1=min(n,min(m,l));
LL v=1,ans=0,s=1,np=n*m%mo*l%mo;
ds[0]=1;
fo(i,1,n1)
{
d[i]=(np-(n-i)*(m-i)%mo*(l-i)%mo+mo)%mo;
ds[i]=ds[i-1]*d[i]%mo;
}
nd[n1]=ksm(ds[n1],mo-2);
fod(i,n1-1,0) nd[i]=nd[i+1]*d[i+1]%mo;
fo(i,1,n1)
{
s=s*(n-i+1)%mo*(m-i+1)%mo*(l-i+1)%mo;
s=s*nd[i]%mo*ds[i-1]%mo;
if(i>=r)
{
ans=(ans+s*v%mo*C(i,r)%mo)%mo;
v=mo-v;
}
}
printf("%lld\n",ans);
}
}