牛客多校第四场 C 题题解

C Easy Counting Problem

C 题题意：给定字符集大小 $\mathrm{\Sigma }\backslash Sigma$，和每个字符出现次数的下限 $\{c_i\}\backslash \{c\_i\backslash \}$，$qq$ 次询问由 $\mathrm{\Sigma }\backslash Sigma$ 中字符构成的长度为 $nn$ 的字符串的个数。$q\le 300q\; \backslash leq\; 300$，$n\le 1\times 10^{7}n\; \backslash leq\; 1\backslash times\; 10^7$，$\sum c_i\le 5\times 10^4\backslash sum\; c\_i\; \backslash leq\; 5\backslash times\; 10^4$，$\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\le 10|\backslash Sigma|\; \backslash leq\; 10$。

解法：对于 $\sum c_i\backslash sum\; c\_i$ 较小的约束条件，可以考虑使用生成函数。本题中由于有次数限制并且对排列计数，因而使用 EGF 指数生成函数。对于第 $ii$ 个字符，其方案对应的 EGF 为

因而对于给定长度的 $nn$，其答案为 ${\displaystyle n![x^n]\prod _{i=1}^{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }}\sum _{j=c_i}^{+\mathrm{\infty }}\frac{x^j}{j!}}\backslash displaystyle\; n![x^n]\backslash prod\_\{i=1\}^\{|\backslash Sigma|\}\; \backslash sum\_\{j=c\_i\}^\{+\backslash infty\}\backslash dfrac\{x^j\}\{j!\}$。考虑如何快速计算：

其中 $S\in \mathrm{\Sigma }S\; \backslash in\; \backslash Sigma$。但是直接计算上式是需要计算 $O(\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }{2}^{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }})O(|\backslash Sigma|2^\{|\backslash Sigma|\})$ 次多项式相乘，不够优秀。但是注意到这一形式与 01 背包非常相似，因而使用背包形式的转移：$f_{i,j}f\_\{i,j\}$ 表示截止前 $ii$ 个字符，已经乘了 $jj$ 个多项式的多项式。其转移形式为 $f_{i,j}\leftarrow f_{i-1,j}+f_{i-1,j-1}g(j)f\_\{i,j\}\; \backslash leftarrow\; f\_\{i-1,j\}+f\_\{i-1,j-1\}g(j)$，其中 ${\displaystyle g(j)=\sum _{k=0}^{c_j-1}\frac{x^k}{k!}}\backslash displaystyle\; g(j)=\backslash sum\_\{k=0\}^\{c\_j-1\}\backslash dfrac\{x^k\}\{k!\}$。 这样只需要计算 $\mathcal{O}(\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^2)\backslash mathcal\; O(|\backslash Sigma|^2)$ 次多项式乘法计算。

因而预处理出 ${\displaystyle f_{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid },i},i\in [0,\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }]}\backslash displaystyle\; f\_\{|\backslash Sigma|,i\},i\; \backslash in\; [0,|\backslash Sigma|]$ 后，容易注意到 $f_{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid },i}f\_\{|\backslash Sigma|,i\}$ 的次数仅为 $\sum c_i\backslash sum\; c\_i$。对于第 $nn$ 项，其答案来源为 $e^{(\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }-i)x}e^\{(|\backslash Sigma|-i)x\}$ 的第 $n-kn-k$ 项与 $f_{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid },i}f\_\{|\backslash Sigma|,i\}$ 的第 $kk$ 项的系数乘积和，即 ${\displaystyle \sum _{k=0}^{\sum c_i}\sum _{i=0}^{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }}(-1{)}^{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }-i}\frac{n!(\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }-i{)}^{n-k}}{(n-k)!}([x^k]f_{\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid },i})}\backslash displaystyle\; \backslash sum\_\{k=0\}^\{\backslash sum\; c\_i\}\backslash sum\_\{i=0\}^\{|\backslash Sigma|\}(-1)^\{|\backslash Sigma|-i\}\backslash dfrac\{n!(|\backslash Sigma|-i)^\{n-k\}\}\{(n-k)!\}\; ([x^k]f\_\{|\backslash Sigma|,i\})$。

因而总的复杂度为 $\mathcal{O}(\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^2\sum c_i\log \sum c_i+q\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\sum c_i)\backslash mathcal\; O(|\backslash Sigma|^2\; \backslash sum\; c\_i\; \backslash log\; \backslash sum\; c\_i+q\; |\backslash Sigma|\backslash sum\; c\_i)$。

void Solve() {
    scanf("%d", &m);
    vector<Poly> p(m + 1);
    p[0] = {1};
    for (int i = 0, x; i < m; ++i) {
        scanf("%d", &x);
        Poly c = Poly(ifac, ifac + x);
        for (int j = i + 1; j; --j)
            p[j] += p[j - 1] * c;
    }
    scanf("%d", &q);
    while (q--) {
        int n, ans = 0;
        scanf("%d", &n);
        if (n < p[m].size()) {
            puts("0");
            continue;
        }
        for (int k = 0; k <= m; ++k) {
            int res = 0;
            for (int i = (int)p[k].size() - 1, pw = POW(m - k, n - i); ~i; --i) {
                res = (res + (ll)p[k][i] * pw % P * ifac[n - i]) % P;
                pw = (ll)pw * (m - k) % P;
            }
            inc(ans, k & 1 ? P - res : res);
        }
        printf("%lld\n", (ll)ans * fac[n] % P);
    }
}