P4491 [HAOI2018]染色

只关心序列的 $N$ 个位置中出现次数恰好为 $S$的颜色种数, 如果恰 好出现了 $S$ 次的颜色有 $K$ 种, 则小 C 会产生 $W_k$ 的愉悦度.
求所有情况总和。

简单证明:

$$f(n)=\sum_{i=0}^n(-1)^i{n\choose i} g(i)\\ g(n)=\sum_{i=0}^n(-1)^i{n\choose i} f(i)$$

只需要证明:

$$f(n)=\sum_{i=0}^nA_{n,i} g(i)\\ A互逆\\ B_{x,y}=\sum A_{x,i}A_{i,y}=\sum_{i=y}^x (-1)^{i+y}{x\choose i}{i\choose y}=\sum_{i=y}^x (-1)^{i+y}\frac{x!}{(x-i)!}\frac{1}{y!(i-y)!}\\=\sum_{i=y}^x (-1)^{i+y}\frac{x!}{y!(x-y)!}\frac{(x-y)!}{(x-i)!(i-y)!}=\sum_{i=y}^x (-1)^{i-y}{x\choose y}{x-y\choose i-y}\\={x\choose y}(1-1)^{x-y}\\ B_{x,y}=[x=y]$$

此题解法

观察$g[k]$保证,

$$g[k]=C(m,k)A(n,sk)/(s!)^k(n-sk)^{m}$$

对于$f(k+1),g[k]$显然记录了$C(k+1,k)次$

$$g(k)=\sum_{i=k}^n{i\choose k} f(i)\\ f(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose k}g(i) \\f(k)k!=\sum_{i=k}^n\frac{(-1)^{i-k}}{(i-k)!}{i!g(i)}\\$$

类似于

$$C[k]=\sum_{i=k}^nA[i-k]B[i]\\ C[k]=\sum_{i=k}^nA[i-k]B^1[n-i]\\$$

• 注意显然需要计算的只是$min(m,n/s)$
  
  代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 4e5 + 10;
const int M = 1e7 + 10;
const int mod = 1004535809;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
const int P = 1004535809;
const int gi = 3;
int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        x >>= 1;
    }
    return res;
}

int fac[M], facinv[M];
void prepare()
{
    fac[0] = 1;
    facinv[0] = 1;
    for (int i = 1; i < M; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    facinv[M - 1] = qpow(fac[M - 1], mod - 2, mod);
    for (int i = M - 2; i >= 1; i--)
        facinv[i] = 1ll * facinv[i + 1] * (i + 1) % mod;
}
int C(int n, int i)
{
    if (n <= 0)
        return 0;
    if (i > n)
        return 0;
    if (i == 0)
        return 1;
    return 1ll * fac[n] * facinv[i] % mod * facinv[n - i] % mod;
}
int rev[N];
void NTT(int *A, int n, int inv)
{
    for (int i = 0; i < n; i++)
        if (i < rev[i])
            swap(A[i], A[rev[i]]);
    for (int l = 1; l < n; l <<= 1)
    {
        int tt = qpow(gi, (P - 1) / (l << 1), P);
        int temp = (inv == 1 ? tt : qpow(tt, P - 2, P));
        for (int i = 0; i < n; i += (l << 1))
        {
            int omega = 1;
            for (int j = 0; j < l; j++, omega = 1ll * omega * temp % P)
            {
                int x = A[i + j], y = 1ll * omega * A[i + j + l] % P;
                A[i + j] = inc(x, y);
                A[i + j + l] = del(x, y);
            }
        }
    }
    int invv = qpow(n, P - 2, P);
    if (inv == -1)
        for (int i = 0; i < n; i++)
            A[i] = 1ll * A[i] * invv % P;
}
int initNTT(int n, int m)
{
    int ML = 1, bit = 0;
    while (ML < n + m)
        ML <<= 1, bit++;
    for (int i = 0; i < ML; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    return ML;
}
void NTTX(int *a, int n, int *b, int m)
{
    int ML = initNTT(n, m);
    NTT(a, ML, 1);
    NTT(b, ML, 1);
    for (int i = 0; i < ML; i++)
        a[i] = 1ll * a[i] * b[i] % P;
    NTT(a, ML, -1);
}

int n, k;
int f[N], g[N];
int main()
{
    prepare();
    int n = read(), m = read(), S = read();
    int lim = min(m, n / S);

    for (int i = 0; i <= lim; i++)
    {
        f[i] = 1ll * C(m, i) * fac[n] % mod * facinv[n - S * i] % mod * qpow(facinv[S], i, mod) % mod * qpow(m - i, n - S * i, mod) % mod;

        f[i] = 1ll * f[i] * fac[i] % mod;

        g[i] = (i & 1) ? mod - facinv[i] : facinv[i];
    }

    reverse(f, f + lim + 1);
    NTTX(f, lim + 1, g, lim + 1);
    reverse(f, f + lim + 1);
    int ans = 0;
    for (int i = 0, w; i <= lim; i++)
    {
        scanf("%d", &w);

        ans = inc(ans, 1ll * f[i] * facinv[i] % mod * w % mod);
    }
    printf("%d", ans);
}

</details>