2022-2023:teams:eager_to_embrace_the_seniors_thigh:c
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:eager_to_embrace_the_seniors_thigh:c [2022/08/02 20:15] 11231123 |
2022-2023:teams:eager_to_embrace_the_seniors_thigh:c [2022/08/07 14:43] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| + | 考虑对每种数构建指数生成函数。对于数 $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)!}$ 。 | ||
2022-2023/teams/eager_to_embrace_the_seniors_thigh/c.1659442544.txt.gz · 最后更改: 2022/08/02 20:15 由 11231123
