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

题解

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

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

\(w_{k} = \binom{n}{k}\binom{m}{k}\binom{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 \binom{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}\binom{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('\n')

#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;

}

巴特西

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

题解

代码

最新文章

热门文章