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 
    
     #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 998244353using 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
     
      >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);    }}