写在前面的话
碍于笔者水平有限，本文缺陷可能比较多，欢迎指正。
前置知识：NTT。
模板
给定 \(f_1,f_2,f_3\dots f_k\) 和 \(a_0,a_1,a_2\dots a_{k-1}\)，求
对 \(998244353\) 取模之后的值。
考虑到上面这个式子和卷积很像，所以我们先想办法将其化为卷积形式。
不妨令 \(f_0=0\)，对于所有 \(i \geq k+1\) 的 \(f_i=0\)。
将上面的式子写为
变为了一个卷积的形式。
设 \(A(x)=\sum_{i=0}^{∞} a_i x^i\)，\(F(x)=\sum_{i=0}^{∞} f_ix^i\)。
将上面的卷积式子写为 \(A(x)=A(x)F(x)\)。
当然，你会发现其实上面的式子只有在 \(n \geq k\) 时才成立，所以 \(A(x)\) 与 \(A(x)F(x)\) 的后 \(k-1\) 项系数可能不同。为了强制使其成立，将式子写为 \(A(x)=A(x)F(x)+P(x)\)。
其中 \(P(x)=\sum_{i=0}^{k-1}p_ix^i\)。
考虑到 \(A\) 前 \(k\) 项已知，\(P\) 最多 \(k\) 项。
所以在已知 \(F\) 的情况下可以求出 \(P\)。
直接求出 \(P(x)\)。
令 \(Q(x)=1-F(x)\)。
答案就是 \(\dfrac{P(x)}{Q(x)}[x^n]\)，考虑怎么求解。
首先将式子分子分母同乘 \(Q(-x)\)，不难发现分母将只会剩下偶次项，令 \(Q_0(x^2)=Q(x)Q(-x)\)，\(P_0(x)=P(x)Q(-x)\)。
如果你熟悉多项式求逆的过程，就可以发现 \(Q_0(x^2)\) 的逆一定也是一个只含偶次项的多项式。
那么 \(P_0(x)\) 的偶次项乘上 \(Q_0(x^2)\) 的逆之后仍为偶次项，奇数同理。
令 \(P_1(x^2)\) 表示 \(P_0(x)\) 的偶次项，\(xP_2(x^2)\) 表示 \(P_0(x)\) 的奇次项。
既然现在这个式子奇偶项互不影响，那么如果 \(n\) 为偶数，就递归求解 \(\dfrac{P_1(x^2)}{Q_0(x^2)}\)，否则求解 \(\dfrac{xP_2(x^2)}{Q_0(x^2)}\)。
显然会求解 \(\log_2 n\) 次，所以总复杂度为 \(O(k \log_2 k \log_2 n)\)。
原文地址：http://www.cnblogs.com/YccQwQ/p/16848301.html
