tag:分治fft，多项式求逆，转置原理

题意

对每个\(k\in[1,n]\)，求出

\[\sum_{i=1}^n(c_i\cdot\Pi_{j=1}^k(a_i+b_j)) \]

题解

设\(F_i(x)=\Pi_{j=1}^i(x+b_j)\)

转化为矩阵形式（式子是从jly的博客贺的）

\[\begin{bmatrix} [x^0]F_1(x)&[x^1]F_1(x)&\cdots&[x^n]F_1(x)\\ [x^0]F_2(x)&[x^1]F_2(x)&\cdots&[x^n]F_2(x)\\ \vdots&\vdots&\ddots&\vdots\\ [x^0]F_n(x)&[x^1]F_n(x)&\cdots&[x^n]F_n(x)\\ \end{bmatrix}\begin{bmatrix} a_1^0&a_2^0&\cdots&a_n^0\\ a_1^1&a_2^1&\cdots&a_n^1\\ \vdots&\vdots&\ddots\vdots\\ a_1^n&a_2^n&\cdots&a_n^n\\ \end{bmatrix}\begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n \end{bmatrix} \]

---

先算右边两个，设结果为\(f\)

\[f_i=\sum_{j=1}^na_j^ic_j \]

也就是多项式\(\sum_{i=1}^n\frac{C_i}{1-a_ix}\)的\([0,n]\)项，用一次分治fft解决

---

然后下一步要用到转置原理，考虑转置后求的是什么

\(ans_i=\sum_{j=1}^n[x_i]F_j(x)f_j\)

也就是多项式\(\sum_{i=1}^nf_iF_i(x)\)的\([0,n]\)项，用分治fft解决

设\(F_{i,j}=\Pi_{k=i}^j(x+b_k)\)，\(A_{l,r}=\sum_{i=l}^rf_iF_{l,i}(x)\)，\(B_{l,r}=F_{l,r}\)

• 叶节点为\(f_i\times(x+b_i)\)

• 递归\((l,mid),(mid+1,r)\)

• \(A_{l,r}=A_{l,mid}+A_{mid+1,r}\times B_{l,r}\)，\(B_{l,r}=B_{l,mid}\times B_{mid+1,r}\)

最后答案多项式为\(ans\)

那么转置后，由于\(B\)与\(f\)无关，所以是不变的

初始化\(A_{1,n}=f\)

• \(A_{l,mid}=A_{l,r}\)，\(A_{mid+1,r}=A_{l,r}\times^TB_{l,mid}\)

• 递归\((l,mid),(mid+1,r)\)

• 叶节点求出\(ans_i=A_{i,i}\times^T(x+b_i)\)，也就是\(ans_i=[x^0]A_{i,i}+b_i\cdot[x^1]A_{i,i}\)

---

放上又调了一个上午的代码