output 1 4 5 2

explanation (1+2x)⋅(1+2x+ x 2 )=1+4x+5 x 2 +2 x 3 (1+2x)⋅(1+2x+x2)=1+4x+5×2+2×3 。 限制与约定 0≤n,m≤ 10 5 0≤n,m≤105 ，保证输入中的系数大于等于 0 0 且小于等于 9 9 。 时间限制： 1s 1s 蒟蒻我暂时只会搞多项式乘法？ n-1次多项式A(x)与m-1次多项式B(x)相乘获得l=n+m-1次多项式c(x) 直接朴素做是n*m的复杂度 对于这题 显然不可做 考虑新学一种算法fft C(x)=A(x)*B(x)

$Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q==i] A_{p}*B_{q}$

$Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q\equiv i (mod\ l)] A_{p}*B_{q}$

$e^{i\pi}=1$

$\omega_l$

$[v\equiv 0(mod\ l)]=\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{v*k}_{l}$

$v\equiv 0(mod\ l)$

$v \not \equiv 0(mod\ l)$

$\frac{1}{l}*\sum_{i=0}^{l-1} \omega_{l}^{i*v}$

$\sum$

$\frac{1-\omega_{l}^{l*v}}{1-\omega_{l}^{v}}=0$

$Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}[p+q-i\equiv 0 (mod\ l)] A_{p}*B_{q}$

$Ci= \sum_{p=0}^{n-1}\sum_{q=0}^{m-1}(\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{(p+q-i)*k}_{l})A_{p}*B_{q}$

$Ci= \frac{1}{l}*\sum_{k=0}^{l-1}\omega^{-i*k}_{l} (\sum_{p=0}^{n-1}\omega^{p*k}_{l}A_{p})*(\sum_{q=0}^{m-1}\omega^{q*k}*B_{q})$

$\sum_{p=0}^{n-1}\omega^{p*k}_{l}A_{p}=A[\omega^{k}_{l}]$

B同理 所以

$ci=\frac{1}{l}*\sum_{k=0}^{l-1}\omega^{-i*k}_{l} *A[\omega^{k}_{l}]*B[\omega^{k}_{l}]$

$dk=A[\omega^{k}_{l}]*B[\omega^{k}_{l}]$

$\sum_{i=0}^{n-1} x^{i}*a_{i}$

$A0(x)=\sum_{i=0,i+=2}^{n-1}x^{i}*a_{i}$

$A0(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{2i}*a_{2i}$

$di=a_{2i}$

$D(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{i}*d_{i}$

$A0(x)=D(x)^{2}$

$A1(x)=\sum_{i=0,i+=2}^{n-1}x^{i}*a_{i}$

$A1(x)=x*\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{2i}*a_{2i+1}$

$ei=a_{2i+1}$

$E(x)=\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}x^{i}*e_{2i}$

$A1(x)=x*E(x^{2})$

$A(x)=A1(x)+A0(x)$

$\frac{l}{2}$

$A(\omega_{l}^{k})=A0(\omega_{l}^{k})+A1(\omega_{l}^{k})$

$A(\omega_{l}^{k})=D(\omega_{l}^{2k})+\omega_{l}^{k}*E(\omega_{l}^{2k})$

$A(\omega_{l}^{k})=D(\omega_{\frac{2}{l}}^{k})+\omega_{l}^{k}*E(\omega_{\frac{2}{l}}^{k})$

$k>=\frac{l}{2}$

$k=k-\frac{l}{2}$

$A(\omega_{l}^{k+\frac{l}{2}})=D(\omega_{l}^{2k+l})+\omega_{l}^{k+\frac{l}{2}}*E(\omega_{l}^{2k+l})$

$\omega_{l}^{\frac{l}{2}}$