[TJOI 2019] 唱、跳、rap 和篮球

LOJ #3106.

挺套路一题

首先感觉可以无脑套容斥……那么就可以来容斥一发……

设$f_{m, t_1, t_2, t_3, t_4}$为有$m$个学生,喜欢唱跳RAP篮球的分别有$t_1, t_2, t_3, t_4$个,的方案数,无脑容斥一下,答案就是$$\sum \limits_{i} (-1)^i\cdot {n – 3i\choose i}\cdot f_{n-4i, a-i, b-i, c-i, d-i}$$

然后考虑$f$怎么算,设最后队列里实际上喜欢唱跳RAP篮球的分别有$w_1, w_2, w_3, w_4$个,那么方案数就是$$\frac{m!}{w_1!w_2!w_3!w_4!}$$

很显然,这个分母是一个卷积的形式,所以卷积一下就好咯

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define pb push_back
#define MOD 998244353
#define MAX_N 1010

int ksm(int x, int y){
    int z = 1;
    for(; y; y >>= 1, x = 1ll * x * x % MOD)
        if(y & 1) z = 1ll * x * z % MOD;
    return z;
}

namespace POLY{
    #define MX 1000010
    #define G 3
    #define iG 332748118
    struct poly : std::vector<int>{};
    int a[MX], b[MX], rev[MX];
    int init(int n){
        int l = 1;
        while(l < n) l <<= 1;
        for(int i = 0; i < l; i++)
            rev[i] = (rev[i>>1] >> 1) | ((i&1) ? (l>>1) : 0);
        return l;
    }
    void ntt(int *P, int l, int opt){
        for(int i = 0; i < l; i++) if(rev[i] > i)
            std::swap(P[i], P[rev[i]]);
        for(int i = 1; i < l; i <<= 1){
            int W = opt > 0 ? G : iG;
            W = ksm(W, (MOD - 1) / (i << 1));
            for(int j = 0, p = i << 1; j < l; j += p)
                for(int k = 0, w = 1; k < i; k++, w = 1ll * w * W % MOD){
                    int x = P[j + k], y = 1ll * P[i + j + k] * w % MOD;
                    P[j + k] = (x + y) % MOD, P[i + j + k] = (x - y) % MOD;
                }
        }
        if(opt < 0){
            int inv = ksm(l, MOD - 2);
            for(int i = 0; i < l; i++) 
                P[i] = 1ll * P[i] * inv % MOD;
        }
    }
    poly operator *(poly x, poly y){
        int l = init(x.size() + y.size() - 1);
        for(int i = 0; i < x.size(); i++) a[i] = x[i];
        for(int i = 0; i < y.size(); i++) b[i] = y[i];
        for(int i = x.size(); i < l; i++) a[i] = 0;
        for(int i = y.size(); i < l; i++) b[i] = 0;
        ntt(a, l, 1); ntt(b, l, 1);
        for(int i = 0; i < l; i++) a[i] = 1ll * a[i] * b[i] % MOD;
        ntt(a, l, -1);
        int lim = std::min(int(x.size() + y.size() - 1), 1001);
        x.resize(lim);
        for(int i = 0; i < lim; i++) x[i] = a[i];
        return x;
    }
    #undef MX
    #undef G
    #undef iG
}
using POLY::poly;

int n, a[4];
int fac[MAX_N], ifac[MAX_N], inv[MAX_N];

int C(int x, int y){
    return 1ll * fac[x] * ifac[y] % MOD * ifac[x-y] % MOD;
}

int calc(int x){
    poly f; f.clear(); f.pb(1);
    for(int i = 0; i < 4; i++){
        poly g; g.resize(a[i] + 1 - x);
        for(int j = 0; j <= a[i] - x; j++) g[j] = ifac[j];
        f = f * g;
    }
    return 1ll * fac[n - 4 * x] * f[n - 4 * x] % MOD;
}

int main(){
    fac[0] = ifac[0] = inv[1] = 1;
    for(int i = 2; i < MAX_N; i++)
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD%i] % MOD;
    for(int i = 1; i < MAX_N; i++)
        fac[i] = 1ll * fac[i-1] * i % MOD,
        ifac[i] = 1ll * ifac[i-1] * inv[i] % MOD;
    scanf("%d%d%d%d%d", &n, &a[0], &a[1], &a[2], &a[3]);
    std::sort(a, a + 4);
    int ans = 0;
    for(int i = 0, t = 1; i <= std::min(n / 4, a[0]); i++, t = -t)
        ans = (ans + 1ll * t * C(n - 3 * i, i) * calc(i) % MOD) % MOD;
    printf("%d\n", (ans + MOD) % MOD);
    return 0;
}

另外律师函警告

发表评论

电子邮件地址不会被公开。 必填项已用*标注