Difficulty：5.0 / Template
题意解析：给定两个多项式，求它们的积。将结果每一项对 998244353\red{998244353}998244353 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
假设积的次数为 n−1n-1n−1，其中 nnn 为 222 的正整数次幂。如果不是的话补成二的正整数次幂就行。
朴素方法是直接枚举两个多项式的每一项，乘起来。但这样的话是 O(n2)O(n^2)O(n2) 的，太慢了。
注意到有一个定理：nnn 个不同的值可以表示出唯一一个不超过 n−1n-1n−1 项式。所以考虑一种神秘的方法：取 nnn 个不同的值分别代入多项式，然后将两个多项式的值乘起来，再用某种方法还原出乘积。
例如两个多项式分别为 x+1x+1x+1 与 x−2x-2x−2，我们取一些值分别代入：
* x=1→x+1=2,x−2=−1,(x+1)(x−2)=−2x=1\rarr x+1=2,x-2=-1,(x+1)(x-2)=-2x=1→x+1=2,x−2=−1,(x+1)(x−2)=−2。
* x=2→x+1=3,x−2=0,(x+1)(x−2)=0x=2\rarr x+1=3,x-2=0,(x+1)(x-2)=0x=2→x+1=3,x−2=0,(x+1)(x−2)=0。
* x=3→x+1=4,x−2=1,(x+1)(x−2)=4x=3\rarr x+1=4,x-2=1,(x+1)(x-2)=4x=3→x+1=4,x−2=1,(x+1)(x−2)=4。
对于 (1,−2),(2,0),(3,4)(1,-2),(2,0),(3,4)(1,−2),(2,0),(3,4) 进行求解，解得多项式为 x2−x−2x^2-x-2x2−x−2。
但我们发现，如果只是代入整数的话，解起来十分困难。
考虑复数领域的单位根 ωn=cos(2πn)+isin(2πn)\omega_n=\cos (\frac{2\pi}{n})+i\sin(\frac{2\pi}{n})ωn =cos(n2π )+isin(n2π )。
这个单位根其实就是 111 逆时针旋转了 1n×360°\frac{1}{n}\times 360\degreen1 ×360°。
这玩意有个性质，就是乘几次方就旋转几倍的度数，也就是说 ωnk\omega_n^kωnk 是 111 逆时针旋转 kn×360°\frac{k}{n}\times 360\degreenk ×360°。
进一步的结论：
* ωn0=ωnn=1\omega_{n}^{0}=\omega_{n}^n=1ωn0 =ωnn =1。
* 对于任意整数 n,kn,kn,k，ω2nk=−ω2nk+n。\omega_{2n}^k=-\omega_{2n}^{k+n}。ω2nk =−ω2nk+n 。
* 对于任意整数 kkk，ωn=ωnkk\omega_{n}=\omega_{nk}^kωn =ωnkk 。
那这个性质有什么用呢？我们可以发现通过单位根，可以很方便地逆向推导出原数组！
假设 f(x)=∑i=0n−1aixif(x)=\sum_{i=0}^{n-1} a_ix^if(x)=∑i=0n−1 ai xi ，代入后的点是 (ωn0,y0),(ωn1,y1),...,(ωnn−1,yn−1)(\omega_{n}^0,y_0),(\omega_n^1,y_1),...,(\omega_n^{n-1},y_{n-1})(ωn0 ,y0 ),(ωn1 ,y1 ),...,(ωnn−1 ,yn−1 ) 。
记多项式 f′(x)=∑i=0n−1yixif'(x)=\sum_{i=0}^{n-1} y_ix^if′(x)=∑i=0n−1 yi xi。
我们把单位根分别的倒数 ωnn,ωnn−1,...,ωn1\omega_n^{n},\omega_n^{n-1},...,\omega_n^1ωnn ,ωnn−1 ,...,ωn1 依次代入，得
(ωnn,z0),(ωnn−1,z1),...,(ωn1,zn−1)(\omega_{n}^{n},z_0),(\omega_n^{n-1},z_1),...,(\omega_n^1,z_{n-1})(ωnn ,z0 ),(ωnn−1 ,z1 ),...,(ωn1 ,zn−1 )。
此时有
zk=∑i=0n−1yiωn−i×k=∑i=0n−1(∑j=0n−1aj×ωni×j×ωni×(−k))=∑i=0n−1aj×(∑j=0n−1ωni×(j−k))z_k\\ =\sum_{i=0}^{n-1}y_i\omega_n^{-i\times k}\\ =\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j\times \omega_n^{i\times j}\times \omega_n^{i\times (-k)})\\ =\sum_{i=0}^{n-1}a_j\times (\sum_{j=0}^{n-1}\omega_n^{i\times (j-k)})
zk =i=0∑n−1 yi ωn−i×k =i=0∑n−1 (j=0∑n−1 aj ×ωni×j ×ωni×(−k) )=i=0∑n−1 aj ×(j=0∑n−1 ωni×(j−k) )
当 j=kj=kj=k 时，里面那一项是 nnn，否则由等比数列求和可知里面那一项是 000。
所以此时 zk=n×akz_k=n\times a_kzk =n×ak 。
我们只需要把每一项 zkz_kzk 求出来，除以 nnn 就能还原出 f(x)f(x)f(x) 了。
但此时如果暴力分别计算 f(x)f(x)f(x) 还是 O(n2)O(n^2)O(n2) 的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
推柿子。
令 f1(x)=∑i=0n2a2ixif_1(x)=\sum_{i=0}^{\frac{n}{2}} a_{2i}x^if1 (x)=∑i=02n a2i xi，f2(x)=∑i=0n2a2i+1xif_2(x)=\sum_{i=0}^{\frac{n}{2}} a_{2i+1}x^if2 (x)=∑i=02n a2i+1 xi，则有 f(x)=f1(x2)+xf2(x2)f(x)=f_1(x^2)+xf_2(x^2)f(x)=f1 (x2)+xf2 (x2)。
令 t=ωnkt=\omega_{n}^{k}t=ωnk ，则有 f(t)=f1(t2)+tf2(t2)f(t)=f_1(t^2)+tf_2(t^2)f(t)=f1 (t2)+tf2 (t2)；
f(−t)=f1(ωn2k+n)+ωnk+n2f2(ωn2k+n)=f1(ωn2k)+ωnk+n2f2(ωn2k+n)=f1(ωn2k)−ωnkf2(ωn2k+n)=f1(t2)−tf2(t2)f(-t)\\ =f_1(\omega_{n}^{2k+n})+\omega_{n}^{k+\frac{n}{2}}f_2(\omega_{n}^{2k+n})\\ =f_1(\omega_{n}^{2k})+\omega_{n}^{k+\frac{n}{2}}f_2(\omega_{n}^{2k+n})\\
=f_1(\omega_{n}^{2k})-\omega_{n}^{k}f_2(\omega_{n}^{2k+n})\\ =f_1(t^2)-tf_2(t^2) f(−t)=f1 (ωn2k+n )+ωnk+2n f2 (ωn2k+n )=f1 (ωn2k )+ωnk+2n f2 (ωn2k+n )=f1 (ωn2k )−ωnk f2 (ωn2k+n )=f1 (t2)−tf2 (t2)
所以，我们只需要得出 f1(t2)f_1(t^2)f1 (t2) 与 f2(t2)f_2(t^2)f2 (t2) 就可以同时知道 f(t)f(t)f(t) 与 f(−t)f(-t)f(−t) 的值！
这样，我们只需要将 k∈[0,n2)k\in[0,\frac{n}{2})k∈[0,2n ) 分别代入 ttt，分别计算出 f1,f2f_1,f_2f1 ,f2 即可得出 nnn 个单位根的值，而 f1f_1f1 与 f2f_2f2 也可以通过这种方式递归。
T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)，主定理一下会发现是 O(nlogn)O(n\log n)O(nlogn) 的。
这样，我们就在 O(nlogn)O(n\log n)O(nlogn) 的复杂度内求出了两个长度为 O(n)O(n)O(n) 的多项式之积！
还没写完。
这周写吧。
