[CCPC2020网络赛]1013-Residual Polynomial

给定初始多项式(f_1(x)=sum_{i=0}^na_ix^i)的系数(a_0dots a_n)，和(b_2dots b_n)和(c_2dots c_n)，后面(f_i(x)=b_if_{i-1}'(x)+c_if_{i-1}(x))，求(f(n))

系数在mod 998244353下

解：观察发现(f_n(x))的系数(a'_kk!=sum_{i=k}^na_ii!s_{i-k})其中我们定义(s_{j})为(b_2...b_n)中选择(j)个，其余的全部选对应的(c)，把它们相乘，所有情况数之和

发现是个卷积的形式（需要把(s)数组翻转一下，然后再搞搞下标），然后搞一波ntt就出来了。

这(s)数组如果直接做是(2^n)的，可以dp是(n^2)的也不行，我们可以利用分治，当(n)小时候为了减小常数可以(O(n^2))但是(n)大的时候就分治，然后通过多项式乘法合并答案，这样子是(O(nlog^2n))的。

总的复杂度是(O(nlog^2n))