P12020

补充一下，三进制 FWT 是不必要的。我们只要凑出系数 $h_0=f_0g_0,h_1=f_0g_1+f_1g_0,h_2=f_1g_1$。这个构造 $f_0g_0,(f_0+f_1)(g_0+g_1),f_1g_1$ 即可，正变换为 $\begin{bmatrix}1&0&0\\1&1&0\\0&1&0\end{bmatrix}$，逆变换为 $\begin{bmatrix}1&0&0\\-1&1&-1\\0&0&1\end{bmatrix}$。这样全程在 long long 运算，显著减少常数。