P12020

xujindong_ · 2025-09-29 11:56:05 · 题解

补充一下，三进制 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 运算，显著减少常数。