?
by 11ofjay @ 2024-03-29 20:24:18
[Link](https://www.luogu.com/article/0s9sytid)
by Implicit @ 2024-03-29 20:32:45
@[hyman00](/user/483879) 对于两个二元多项式 $F(x,y),G(x,y)$ 要计算卷积的话，可以将其看作两个关于 $x$ 的多项式，但系数是关于 $y$ 的多项式。
两个关于 $x$ 的多项式要做卷积，这个我们是会的，直接做 FFT 即可。不过 FFT 的时候系数是关于 $y$ 的多项式，所以做 FFT 的复杂度是 $\Theta(n \log n)\times \Theta(n) = \Theta(n^2 \log n)$。
by NaCly_Fish @ 2024-03-29 20:34:55
直接考虑设 $x,y$ 的**最高次**分别为 $n,m$，考虑 $x^ay^b\times x^cy^d\to x^{a+c}y^{b+d}$ 的过程，发现若把 $(a,b)$ 想想成矩阵中的 $(a,b)$ 位置，直接刻画为在 $a(m+1)+b$ 处有系数 $f_{a,b}$，然后直接 **NTT**，再逆回来，最终答案就是两个二元多项式卷积。
令 $N=nm$，复杂度为 $O(N\log N)$
by masterhuang @ 2024-03-30 09:19:11