题目大意
有一个长度为 $n$ 的数列 $a_1$~$a_n$，进行 $m$ 次操作，每次操作给定一个整数 $k$（$1 \leq k \leq 3$），将 $a$ 数列变成 $b$ 数列：
求最终的数列。
$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$ 数列，那么它们的生成函数是这样的：
一次操作相当于给 $A$ 乘一个多项式，那么操作顺序是不要紧的，因此三种操作分别对应三个多项式：$(\sum x^i)^{m_1}$、$(\sum x^{2i})^{m_2}$、$(\sum x^{3i})^{m_3}$。
然后这三个多项式都可以先算出来（系数都是组合数），那么对于原序列就是 3 次 NTT 的事儿。
时间 $O(n \log n)$