【2019 Multi-University 1 L】Sequence 题解

题目大意

  有一个长度为 $n$ 的数列 $a_1$~$a_n$，进行 $m$ 次操作，每次操作给定一个整数 $k$（$1 \leq k \leq 3$），将 $a$ 数列变成 $b$ 数列：

$$b_i=\sum_{1 \leq i-kj \leq i} a_{i-kj}$$

  求最终的数列。

  $1 \leq n \leq 10^5,\ \ 1 \leq m \leq 10^6,\ \ 1 \leq a_i \leq 10^9$

题解

  您好，您的多项式能力为 0，请做题

  先是有一个经典的转换：设 $a$ 数列的生成函数为 $A=\sum a_ix^i$，考虑 $a$ 数列经过一次 $k$ 操作变成 $b$ 数列，那么它们的生成函数是这样的：

$$B=\sum b_ix^i=(\sum a_ix^i)(\sum x^{ik})=A\sum x^{ik}$$

  一次操作相当于给 $A$ 乘一个多项式，那么操作顺序是不要紧的，因此三种操作分别对应三个多项式：$(\sum x^i)^{m_1}$、$(\sum x^{2i})^{m_2}$、$(\sum x^{3i})^{m_3}$。
  然后这三个多项式都可以先算出来（系数都是组合数），那么对于原序列就是 3 次 NTT 的事儿。

  时间 $O(n \log n)$