问题
给出两个幂级数 (f,g) ，求
[h=sum _isum _jx^{ioplus j}f_ig_j
]
其中 (oplus) 是可拆分的位运算。
算法
由于位运算具有独立性，可以一位位地考虑。
设 (f=(f_0,f_1)) ，即最高位为 0 的部分和最高位为 1 的部分。我们希望把这个卷积转化为点积来做。即
[Tegin{bmatrix}f_0 \f_1 end{bmatrix}cdot Tegin{bmatrix}g_0 \g_1 end{bmatrix}=Tegin{bmatrix}h_0 \h_1 end{bmatrix}
]
按照 (f,g,h) 的对应关系，对比系数容易得到 (T) 。
那么我们就可以先对 (f,g) 递归进行上述变换，然后再点积起来，逆变换回去，这样就能得到我们需要的 (h) 。显然逆变换可以直接用矩阵 (T^{-1}) 做同样的操作。
复杂度为 (O(nk^2log n)) ，(k) 为位状态数。
拓展
上面的过程只用到了位运算的可拆分性，所以可以尝试拓展一下。例如更高进制的位运算卷积，可以用完全一样的方法来做。做之前只要定义好位的运算即可。例如 [清华集训2016]石家庄的工人阶级队伍比较坚强 中的三进制卷积，类比二进制异或，定义三进制不进位加法，构造出输赢的异或关系即可。