2022-2023:teams:eager_to_embrace_the_seniors_thigh:c
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:eager_to_embrace_the_seniors_thigh:c [2022/08/07 14:33] 11231123 [题解] |
2022-2023:teams:eager_to_embrace_the_seniors_thigh:c [2022/08/07 14:43] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 那么答案就可以写作 $ans = n![x^n]\prod_{i=1}^{w}{(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!}}}})}$ | + | 考虑变化后面的式子为 $\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.1659854038.txt.gz · 最后更改: 2022/08/07 14:33 由 11231123
