题解 P5400 【[CTS2019]随机立方体】

题目Link:[P5400 [CTS2019]随机立方体](https://www.luogu.org/problemnew/show/P5400) MC大法好!**MC造图**解此题! 有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标**至少有一维相同**的其他格子上的数都要大的话，我们就称它是极大的。 将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求**恰有** $k$ 个极大的数的概率。答案对 $998244353$（一个质数）取模。 多组数据。 $1\le n,m,l\le 5000000$，$1\le k\le 100$，$1\le T\le 10$ 设$G(k)$是求**恰有** $k$ 个极大的数的**方案数**。 首先这个**恰好**非常难受,我们按照套路采用**重复统计**,即:首先弄出$k$个极大值,然后放任自流,这样方案数称为$F(k)$。 容易得到:没有两个级大数会在同一个平面上,所以最多有$min(n,m,l)$个级大数,设$R=min(n,m,l)$。 这里要特判一下,如果$k>R$则输出0。 那么就能得到$F(k)=\sum\limits_{i=k}^R\dbinom{i}{k}G(i)$ 解释一下为什么:如果一个方案中有$i$个极大值,那么你只要选中其中的$k$个,这个方案就会被统计一次,随意一共被统计了$\dbinom{i}{k}$次。 所以这里要再次声明:所谓的$F(k)$并**不是**至少有$k$个极大的数的方案数,否则的话$F(k)-F(k-1)$就是答案了。 (这个错误好像大多数题解都有犯过,我初学的时候一直认为$ANS=F(k)-F(k-1)$,WA了一版之后才意识到错误) [$\text{二项式反演}$](https://www.luogu.org/blog/command-block/yi-suo-ji-guai-di-fan-yan)可得$G(k)=\sum\limits_{i=k}^R(-1)^{i-k}\dbinom{i}{k}F(i)$ 只用求$G(k)$,所以上述式子我们直接暴力算复杂度正确。 问题在于如何求出$F(k...R)$。 为了方便,这里设$T=nml$. $F(k)=$选出$k$个级大数位置的方案数$*$被级大数影响的数的填写方法$*$不被影响的数的填写方法。 - 选出$k$个级大数的方案数 没有两个级大数会在同一个平面上,所以这个东西并不是简单地等于$T^{\underline{k}}$ 第一个级大数放置之后,有三个平面的数必须小于该数,其他的位置并没有影响。 所以可选的位置变成了$(n-1)(m-1)(l-1)$个,我们发现就是把原来的空间从各个方向分别削去了1,变成了子问题。 那么总的方案数是$\frac{1}{k!}\prod\limits_{i=0}^{k-1}(n-i)(m-i)(l-i)$,因为这些极大值之间是无序的。 - 被级大数影响的数的填写方法 本题最麻烦的东西。 这$k$个极大值影响的的数的个数是可以求的,即为$T-(n-k)(m-k)(l-k)$ 设$G_i=T-(n-i)(m-i)(l-i)$. 我们先要选出$G_k$个数值,这部分方案数是$\dbinom{T}{G_k}$. 此外,我们还要考虑这$G_k$个数怎么摆放。 第一个级大数放置之后,有三个平面的数必须小于该数,其他的位置并没有影响。 第二个级大数放置之后,有三个平面的数必须小于该数,其他的位置并没有影响。 问题在于这六个平面**有交**,那样子是无法分析的。 不过我们发现,假如第一个数小于第二个数的话,那么第一个数控制的三个平面必然都小于第二个数,也就是说,**没有影响**。 容易发现,对于一种合法方案,我们可以任意交换两个面,交换后仍然合法。 那么我们前面已经钦定了$k$个极大值的位置,那么我们把它们一顿swap,得到下图: 由于我们在这里钦定了极大值的相对大小,所以这里还要乘上$(k!)$   彩色羊毛表示极大值,玻璃表示这些极大值的控制范围。 那么如图,对应颜色玻璃玻璃就是该颜色羊毛的控制区域。 设$\text{黄}<\text{蓝}<\text{红}<\text{绿}$,反正是可以随便交换的。 那么,对于蓝色的区域,它们**只需要**满足小于蓝色羊毛就好了。 我们可以容易地算出每个区域的大小,比如蓝色区域的大小是$(n-1)(m-1)(l-1)-(n-2)(m-2)(l-2)$ 为了方便,我们设$g_i=(n-i)(m-i)(l-i)$. 那么第$i$层(从外到里)的大小为$g_{i-1}-g_i$ 我们把这个东西**从里到外**一层一层剥开来理解: 显而易见的,值$nml$一定是极大值,所以$\text{绿}=nml$ 这里$k=4$。 我们知道$|\text{绿}|=g_3-g_4$,数值上有全部的$G_4$个可随意排列。 那么方案总数是$A_{G_4-1}^{g_3-g_4-1}=\dfrac{(G_4-1)!}{(G_4-1-(g_3-g_4-1))!}=\dfrac{(G_4-1)!}{G_3!}$. (z这里之所以减1是因为我们钦定了一个数作为极大值) 对于下一层,可以看做变成了$k$小了1(从里面被剥掉了一层)的子问题。 所以总方案数是$\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_{i-1}!}$ 这部分的总方案数乘起来就是$k!\dbinom{N}{G_k}\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_{i-1}!}$ - 其他的数的填法 放任自流就好了,剩下$g_k$个数,那么直接$g_k!$即可。 我们把公式汇总一下: $F(k)=\frac{1}{k!}\prod\limits_{i=0}^{k-1}g_ig_k!k!\dbinom{N}{G_k}\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_{i-1}!}$ $=\dfrac{N!}{g_k!G_k!}\prod\limits_{i=0}^{k-1}g_ig_k!\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_{i-1}!}$ 因为我们这里算的是方案数,这里除以$N!$就是概率。 $=\dfrac{1}{G_k!}\prod\limits_{i=0}^{k-1}g_i\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_{i-1}!}$ 那么到了这里,你会注意到$G_k$是$O(nk)$级别的,那么暴力预处理所有的$G!$就能得到80分。 我们发现式子的前面有一个$\dfrac{1}{G_k!}$,把它塞进后面的$\prod$里面。 $=\prod\limits_{i=0}^{k-1}g_iG_0!\prod\limits_{i=1}^k\dfrac{(G_i-1)!}{G_i!}$ $=\prod\limits_{i=0}^{k-1}g_iG_0!\prod\limits_{i=1}^k\dfrac{1}{G_i}$ 由于$G_0!=0!=1$得到$F(k)=\prod\limits_{i=0}^{k-1}g_i\prod\limits_{i=1}^k\dfrac{1}{G_i}$ 我们发现这个东西十分的简洁,不过我们对于$G$要采用线性求逆元才行,否则复杂度多一个log。 求出$F$之后暴力二项式反演即可。 总复杂度$O((n+k)T)$(注意卡常数) 由于这题时间限制很松,我就$O((n+k)Tlog(mod))$艹过去了…… ```cpp #include<algorithm> #include<cstdio> #define mod 998244353 #define MaxN 5000500 using namespace std; long long powM(long long a,long long t=mod-2) { a=(a%mod+mod)%mod; long long ans=1; while(t){ if(t&1)ans=(ans*a)%mod; a=(a*a)%mod; t>>=1; }return ans; } long long fac[MaxN],inv[MaxN]; void Init() { fac[0]=fac[1]=inv[0]=inv[1]=1; for (int i=2;i<=5000000;i++){ fac[i]=fac[i-1]*i%mod; inv[i]=(mod-mod/i)*inv[mod%i]%mod; }for (int i=2;i<=5000000;i++) inv[i]=inv[i]*inv[i-1]%mod; } long long C(int n,int m) {return fac[n]*inv[n-m]%mod*inv[m]%mod;} int F[MaxN],G[MaxN],Gl[MaxN],R,n,m,l,k,T; inline int g(int k) {return 1ll*(n-k)*(m-k)%mod*(l-k)%mod;} int main() { Init();Gl[0]=1; int qt; scanf("%d",&qt); while(qt--){ scanf("%d%d%d%d",&n,&m,&l,&k); R=min(n,min(m,l)); if (k>R){printf("0\n");continue;} T=1ll*n*m%mod*l%mod; for (int i=1;i<=R;i++) G[i]=powM((T-g(i)+mod)%mod); long long buf=1; for (int i=1;i<=R;i++) F[i]=buf=buf*g(i-1)%mod*G[i]%mod; buf=0; for (int i=k;i<=R;i++) if ((i-k)&1) buf=(buf-C(i,k)*F[i])%mod; else buf=(buf+C(i,k)*F[i])%mod; printf("%lld\n",(buf+mod)%mod); }return 0; } ```