CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== Easy Counting Problem ======

==== 题意 ====

$1$ 到 $w$ 这 $w$ 种数每种至少在字符串中出现 $c_1, c_2, ……, c_w$ 次， $q$ 次询问，每次给出一个 $n$ ，求长度恰好为 $n$ 的字符串有多少种。

$w\le 10, q\le 300, n\le 10^7, \sum{c_i}\le 5*10^4$

==== 题解 ====

考虑对每种数构建指数生成函数。对于数 $i$ 显然有 $ F_i = \sum_{j \ge c_i}{\frac{x^j}{j!}} $ 。

然后对于每个询问的答案就是 $ ans = n![x^n]\prod_{i=1}^{w}{F_i} $ 。

我们注意到这个题 $\sum{c_i}$ 很小但是 $n$ 很大，考虑将 $F_i$ 写成 $F_i = \sum_{j\ge c_i}{\frac{x^j}{j!}} = e^x-\sum_{j=0}^{c_i-1}{\frac{x^j}{j!}}$ 。

那么答案就可以写作 $ans = n![x^n]\prod_{i=1}^{w}{(e^x-\sum_{j=0}^{c_i-1}{\frac{x^j}{j!}})}$ 。

考虑变化后面的式子为 $\sum_{i=0}^{w}{e^{ix}(-1)^{w-i}(\sum_{|S|=w-i}{\prod_{j\in S}{\sum_{k=0}^{c_j-1}{\frac{x^k}{k!}}}})}$ 。定义 $f_{i,j}$ 表示前 $i$ 种数里面选了 $j$ 个的 $\sum_{k=0}^{c_h-1}{\frac{x^k}{k!}}$ 的乘积的和，此时式子可以写作 $\sum_{i=0}^{w}{e^{ix}(-1)^{w-i}f_{w,w-i}}$ 。

求 $f$ 的时候考虑按照背包DP的方式求解，每次转移的时候做一次卷积。

最后对于每个询问的答案就是 $ans = n!\sum_{i=0}^{w}{\sum_{k=0}^{\sum_{c_i}}{[x^{n-k}]e^{(w-i)x}[x^k]f_{w,i}(-1)^i}}$ 。其中 $[x^{n-k}]e^{(w-i)x}=\frac{(w-i)^{n-k}}{(n-k)!}$ 。

CVBB ACM Team

用户工具

站点工具

页面工具