随机立方体[CTS2019]

发表于 分类于 ，

题目链接

链接

题意

有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。对 $998244353$ 取模。

$T\leq 10,n,m,l\leq 5\times 10^6,k\leq 100$。

题解

$k\leq100$？似乎就是用来迷惑人的吧。。。

“恰有”非常难搞，那就考虑容斥，变成钦定 $k$ 个为极大，设此时答案为 $f_k$。

那么二项式反演一下，可得到最后的答案为 ：$\sum_{i=k}^{\min{n,m,l}}(-1)^{i-k}\binom{i}{k}f_i$。

设 $w=\min{n,m,l}$，接下来考虑如何求 $f _ k$。

第一步是要钦定 $k$ 个极大的点，且这 $k$ 个极大的点已经按从小到大的顺序排好。

显然，这 $k$ 个极大的点的 $x$ 坐标都互不相同，$y,z$ 同理。那么也就是有 $\binom{n}{i}\binom{m}{i}\binom{l}{i}(i!)^3$ 种情况。

然后在 $1\sim nml$ 中选一些数，填到跟这 $k$ 个点有关系的点上去。什么叫有关系，就是坐标跟这 $k$ 个中的任意一点至少有一维相同的点就能有关系。这些点有多少个呢？显然用总方案减去不合法的，即没有一维和这 $k$ 个点相同。设为 $s_k$，则有：$s_k=nml-(n-k)(m-k)(l-k)$。那么选的方案数就是 $\binom{nml}{s_k}$。

接着，除了这 $s_k$ 个点以外的点就可以乱选了，也就是 $(nml-s_k)!$ 种。

最后要把这 $s_k$ 中颜色填上去，使得钦定的 $k$ 个点为极大点，设这时的答案为 $g_k$。

那么有：

$$f_i=\frac{\binom{nml}{s_k}(nml-s_k)!\binom{n}{i}\binom{m}{i}\binom{l}{i}(i!)^3g_i}{(nml)!}$$

除以 $(nml)!$ 是因为我们算的是概率。

接下来就只需要看这个 $g_k$ 如何算了，考虑有 $g_{k-1}$ 递推过来

考虑从大到小填这个极大值进去。首先极大值这个位置已经确定了，现在我们还有 $s_k-1$ 个数可以选择，需要选一些数使得最后剩下 $s_{k-1}$ 个数，那么就有 $\frac{(s_k-1)!}{s_{k-1}!}$ 种情况。

最后有 $g_k=\prod_{i=1}^k{\frac{(s_i-1)!}{s_{i-1}!}}$。

代入答案，化简得：

$$Ans=\sum_{i=k}^{w}(-1)^{i-k}\binom{i}{k}\binom{n}{i}\binom{m}{i}\binom{l}{i}(i!)^3\prod_{j=1}^i\frac{1}{s_j}$$

线性处理 $\prod_{j=1}^is_j$ 的逆元即可。

时间复杂度 $O(Tw)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
const int N=5e6+5;
ll fac[N],inv[N];

inline void init(int n)
{
    fac[0]=1;
    fo(i,1,n) fac[i]=fac[i-1]*i%mod;
    inv[n]=Pow(fac[n],mod-2);
    fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
inline ll C(int n,int m)
{
    if(n<0||m<0||n-m<0) return 0;
    return Mul(fac[n],Mul(inv[m],inv[n-m]));
}
ll sum,ss,ans,s[N],g[N];
int n,m,l,k,w;
inline ll calc(int i)
{
    return inv[n-i]*inv[m-i]%mod*inv[l-i]%mod;
}
int main()
{
    init(5000000);
    CASET
    {
        n=read(); m=read(); l=read(); k=read();
        sum=Mul(l,Mul(n,m));
        w=min(min(n,m),l);
        ss=1;
        fo(i,1,w) s[i]=Dec(sum,Mul(Mul(n-i,m-i),l-i)),ss=Mul(ss,s[i]);
        ss=Pow(ss,mod-2); g[w]=ss;
        fd(i,w,1) g[i-1]=g[i]*s[i]%mod;
        ans=0;
        fo(i,k,w) ans=Add(ans,Mul(Mul(((i-k)&1)?mod-1:1,C(i,k)),g[i])*calc(i)%mod);
        ans=Mul(Mul(ans,fac[n]),Mul(fac[m],fac[l]));
        printf("%lld\n",ans);
    }
    return 0;
}