P4491 [HAOI] 染色

P4491 [HAOI] 染色

题面

题目链接

解法

考虑朴素的做法。容易想到钦定$k$个颜色出现次数恰好为$S$，其他颜色随便填并容斥。求出$k \in [0, \min(m,n/2)]$即可。

$$F[k]=\binom{m}{k}\binom{n}{ks}\frac{(ks)!}{(s!)^k}(m-k)^{n-ks}$$

思考这样重复计算到的部分。设$G[i]$为真正的答案，那么有

$$F[k]=\sum_{i=k}^n\binom{i}{k}G[i]$$

使用二项式反演，得到

$$G[k]=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}F[i]$$

将组合数展开

$$G[k]=\sum_{i=k}^n(-1)^{i-k}\frac{i!}{k!(i-k)!}F[i]$$

对$1004535809$取模，你想到了什么？

$$G[k]=\frac{1}{k!}\sum_{i=k}^ni!F[i]\times\frac{(-1)^{i-k}}{(i-k)!}$$

于是$O(n+m\log m)$算出$F[0\cdots m]$，然后NTT做卷积差求出$G[0\cdots m]$即可。

AC代码

/**
 * @file:           P4491.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4491
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 1 << 20;
const int MAXM = 1e7 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1004535809;
namespace maths {
int add(int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}
int sub(int x, int y) {
    x -= y;
    return x < 0 ? x + MOD : x;
}
int qpow(int x, int y, int p = MOD) {
    int ret = 1;
    for (; y; y >>= 1, x = x * x % p)
        if (y & 1)
            ret = ret * x % p;
    return ret;
}
template <class _Tp>
void change(_Tp* f, int len) {
    static int rev[MAXN] = {};
    for (int i = 0; i < len; ++i) {
        rev[i] = rev[i >> 1] >> 1;
        if (i & 1)
            rev[i] |= len >> 1;
    }
    for (int i = 0; i < len; ++i)
        if (i < rev[i])
            swap(f[i], f[rev[i]]);
}
void ntt(int* f, int len, int on) {
    change(f, len);
    for (int h = 2; h <= len; h <<= 1) {
        int gn = qpow(3, (MOD - 1) / h);
        for (int j = 0; j < len; j += h) {
            int g = 1;
            for (int k = j; k < j + h / 2; ++k) {
                int u = f[k], t = g * f[k + h / 2] % MOD;
                f[k] = add(u, t), f[k + h / 2] = sub(u, t);
                g = g * gn % MOD;
            }
        }
    }
    if (on == -1) {
        reverse(f + 1, f + len);
        int inv = qpow(len, MOD - 2);
        for (int i = 0; i < len; ++i)
            f[i] = f[i] * inv % MOD;
    }
}
};  // namespace maths
using namespace maths;
int n, m, s, w[MAXN];
int a[MAXN], b[MAXN], f[MAXN], g[MAXN];
int fac[MAXM], inv[MAXM];
int binom(int x, int y) {
    return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
signed main() {
    read(n), read(m), read(s);
    for (int i = 0; i <= m; ++i)
        read(w[i]);
    fac[0] = 1;
    for (int i = 1; i < MAXM; ++i)
        fac[i] = fac[i - 1] * i % MOD;
    inv[MAXM - 1] = qpow(fac[MAXM - 1], MOD - 2);
    for (int i = MAXM - 2; ~i; --i)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    int mx = min(m, n / s);
    for (int i = 0; i <= mx; ++i) {
        f[i] = binom(m, i) * binom(n, i * s) % MOD * fac[i * s] % MOD
             * qpow(inv[s], i) % MOD * qpow(m - i, n - i * s) % MOD;
    }
    for (int i = 0; i <= mx; ++i) {
        a[i] = fac[i] * f[i] % MOD;
        b[i] = (i & 1) ? sub(MOD, inv[i]) : inv[i];
    }
    reverse(a, a + mx + 1);
    int len = 1;
    while (len <= mx + mx + 1)
        len <<= 1;
    ntt(a, len, 1);
    ntt(b, len, 1);
    for (int i = 0; i < len; ++i)
        g[i] = a[i] * b[i] % MOD;
    ntt(g, len, -1);
    reverse(g, g + mx + 1);
    for (int i = 0; i <= mx; ++i)
        g[i] = g[i] * inv[i] % MOD;
    int ans = 0;
    for (int i = 0; i <= mx; ++i)
        ans = add(ans, g[i] * w[i] % MOD);
    write(ans), putchar('\n');
    return 0;
}