毒瘤计数题

我们设\(dp_i\)表示至少有\(i\)个极大数字的概率，\(ans_i\)表示恰好有\(i\)个极大数的概率，\(mi=Min(n,m,l)\)

易知：

\[dp_i=\sum_{j=i}^{mi} ans_j \tbinom{j}{i}\]

由二项式反演得：

\[ans_i=\sum_{j=i}^{mi} dp_j \tbinom{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可知这时候贡献要乘上\(\tbinom{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\)个极大值点后影响到的平面的交集的方案数，易知：

\[ \begin{align*} h_i & = \frac{(g_i-1)!}{g_{i-1}!} \times h_{i-1} \\ & = \prod_{j=0}^{i-1} \frac{(g_{j+1}-1)!}{g_j!} \end{align*} \]

我们这是就珂以求出\(dp_i \times N!\)了，即至少有\(i\)个极大数字的种类数，那么\(dp_i\)也就珂以求出

\[ \begin{align*} dp_i*N! & = \tbinom{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}^i\frac{1}{g_j!} \\ & = N! f_i \prod_{j=1}^i\frac{1}{g_j} \end{align*} \]

\[dp_i=f_i \prod_{j=1}^i\frac{1}{g_j}\]

这样我们就能快速求出答案了，复杂度为\(O(T Min(n_i,m_i,l_i))\)

#include 
    
     #define N 5000005#define mod 998244353 #define getchar ncusing 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
     
      >=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
      
       mi)        {            puts("0");            continue;        }        f[0]=1;        for(register int i=0;i