前半部分是个 sam 板子按下不提，我们来做后半部分。

给定长度为 $n$ 的序列 $a_1 \sim a_n$，对于 $k \in [0,n]$ 求出 $ans_k=\sum_{i=1}^{n}\binom{a_i}{k}$，答案对于 $998244353$ 取模。

$1 \leq n \leq 10^5,0 \leq a_i<998244353$。

组合数改成下降幂后施斯特林反演：

$$ \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)$。