ez problem 8
luogu_gza
·
·
算法·理论
给定长度为 n 的序列 a_1 \sim a_n,对于 k \in [0,n] 求出 ans_k=\sum_{i=1}^{n}\binom{a_i}{k},答案对于 998244353 取模。
本题为 qoj23597 转化后题意,这个题的前半部分是个字符串问题,我们略过不谈。
::::info[solution]
组合数改成下降幂后施斯特林反演:
$$
\begin{aligned}
ans_k&=\sum_{i=1}^{n}\binom{a_i}{k} \\
&=\frac{1}{k!}\sum_{i=1}^{n}a_i^{\underline{k}} \\
&=\frac{1}{k!}\sum_{i=1}^{n}\sum_{j=0}^{k}s(k,j)(-1)^{k-j}a_i^j \\
&=\frac{1}{k!}\sum_{j=0}^{k}s(k,j)(-1)^{k-j}\sum_{i=1}^{n}a_i^j
\end{aligned}
$$
问题自然的变成了两部分,求 $f_j=\sum_{i=1}^{n}a_i^j$ 与求 $\sum_{j=0}^{k}s(k,j)(-1)^{k-j}f_j$。
第一部分是等幂和,我们逆用 ez problem 3 的结论,$$\frac 1j f_j=\frac 1j \sum_{i=0}^{m}a_i^j=[x^j]\ln(\prod_{i=1}^{m}(1-a_ix))$$,分治乘即可。
第二部分中 $s(k,j)(-1)^{k-j}$ 是带符号第一类斯特林数,以它的 gf 重写这个问题:给定多项式 $A$ 和一族多项式 $F_k=\prod_{i=0}^{k-1}(x-i)$,要对 $k \in [0,n]$ 求 $ans_k=\sum_{i=0}^{n}[x^i]F_k[x^i]A$。
施转置原理,我们欲解决:给定一组系数 $y_0 \sim y_n$,计算多项式 $\sum_{i=0}^{n}y_iF_i(x)$。
施以分治,令 $P_{l,r}(x)=\prod_{i=l}^{r-1}(x-i)$,若 $l=r$ 则 $P_{l,r}(x)$ 被定义为 $1$。令 $Q_{l,r}(x)=\sum_{i=l}^{r-1}y_k\prod_{j=l}^{i-1}(x-j)$。取 $mid=\lfloor \frac{l+r}{2} \rfloor$,显然有 $P_{l,r}=P_{l,mid}P_{mid,r},Q_{l,r}=Q_{l,mid}+P_{l,mid}Q_{mid,r}$。
总时间复杂度 $O(n \log^2 n)$。
::::