【LOJ】#3119. 「CTS2019 | CTSC2019」随机立方体

题解

用容斥，算至少K个极大值的方案数

我们先钦定每一维的K个数出来，然后再算上排列顺序是

(w_{k} = inom{n}{k}inom{m}{k}inom{l}{k}(k!)^3)

然后有((n - k)(m - k)(l - k))是可以随便填的

设(all = nml,v_k = nml - (n - k)(m - k)(l - k))

设剩下的数填的方案是(h_k)

那么答案就是(w_kh_k inom{all}{all - v_{k}}(all - v_k)!)

我们可以发现应该是每次选一个最大的作为极大值，然后再选出(v[k] - v[k - 1] - 1)作为极大值的陪葬而不能让它们去侵占下一个极大值的位置

所以(h_{k} = h_{k - 1}frac{(v_{k} - 1)!}{v_{k - 1} !})

然后至少k个的答案就是

(w_{k}frac{all!}{v_{k}!}prod_{i = 1}^{k} frac{(v_{k} - 1)!}{v_{k - 1}!})

我们发现后面那部分可以约掉很多

最后就是

(all!w_{k}prod_{i = 1}^{k}frac{1}{v_k})

最后应该除下来一个(all!)因为算的是概率

设至少k个的答案是(f_k)

最后答案就是

(ans = sum_{i = K}^{min(N,M,L)}(-1)^{i - K}inom{i}{K}f_{k})

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 2005
#define ba 47
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
    	if(c == '-') f = -1;
    	c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 +c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 998244353;
const int V = 5000000;
int N,M,L,K;
int fac[V + 5],invfac[V + 5],w[V + 5],v[V + 5],inv[V + 5];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
int mul3(int a,int b,int c) {
    return mul(mul(a,b),c);
}
void update(int &x,int y) {
    x = inc(x,y);
}
int C(int n,int m) {
    if(n < m) return 0;
    else return mul(fac[n],mul(invfac[m],invfac[n - m]));
}
int fpow(int x,int c) {
    int res = 1,t = x;
    while(c) {
        if(c & 1) res = mul(res,t);
        t = mul(t,t);
        c >>= 1;
    }
    return res;
}
void pre_process() {
    fac[0] = 1;
    for(int i = 1 ; i <= V ; ++i) fac[i] = mul(fac[i - 1],i);
    invfac[V] = fpow(fac[V],MOD - 2);
    for(int i = V - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
}
void Solve() {
    read(N);read(M);read(L);read(K);
    int T = min(min(N,M),L);
    for(int i = 0 ; i <= T ; ++i) {
        int t = mul3(fac[i],fac[i],fac[i]);
        w[i] = mul3(C(N,i),C(M,i),C(L,i));
        w[i] = mul(w[i],t);
    }
    int ALL = mul3(N,M,L);
    for(int i = 0 ; i <= T ; ++i) {
        int t = mul3(N - i,M - i,L - i);
        v[i] = inc(ALL,MOD - t);
    }
    int p = 1;
    for(int i = 1 ; i <= T ; ++i) {
        p = mul(p,v[i]);
    }
    inv[T] = fpow(p,MOD - 2);
    for(int i = T - 1 ; i >= 1 ; --i) inv[i] = mul(inv[i + 1],v[i + 1]);
    int res = 0;
    for(int i = K ; i <= T ; ++i) {
        if((i - K) & 1) update(res,MOD - mul3(C(i,K),inv[i],w[i]));
        else update(res,mul3(C(i,K),inv[i],w[i]));
    }
    out(res);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    pre_process();
    int T;
    read(T);
    while(T--) Solve();
    return 0;
}