位运算卷积

参考资料：jz姐姐的题解

定义

\[\begin{aligned} mex(a,b)=\sum_{i=0}^{k-1}mex(a_i,b_i)3^i \end{aligned} \]

其中\(a_i,b_i\)表示\(a,b\)的三进制第\(i\)位，求

\[\begin{aligned} c_k=\sum_{mex(i,j)=k}a_i,b_j \end{aligned} \]

我们先把柿子列出来

\[\begin{aligned} &c_0 = a_1b_2 + a_2b_1 + a_1b_1 + a_2b_2\\ &c_1 = a_0b_0 + a_0b_2 + a_2b_0 \\ &c_2 = a_0b_1 + a_1b_0 \end{aligned} \]

然后把左边每一项都凑成可以表示成右边两个相同形式的积的形式，发现\(3\)位不够，得多加一位，而且还得额外搞一个\(c_3\)

\[\begin{aligned} &c_0 = (a_1+a_2)(b_1+b_2) \\ &c_0 + c_1 + c_2 = (a_0 + a_1 + a_2)(b_0 + b_1 + b_2) \\ &c_3 = a_2b_2 \\ &c_1 + c_3 = (a_0 + a_2)(b_0 + b_2) \end{aligned} \]

这就是它的\(FWT\)了。由于我们需要的是四位，而题中是三位，所以得三进制转四进制最后转三进制回去

复杂度\(O(k4^k)\)

代码如下

inline void FWT(int &a,int &b,int &c,int &d){
        int x0=a,x1=b,x2=c;
        a=x1+x2,b=x0+x1+x2,c=x0+x2,d=x2;
}
inline void IFWT(int &a,int &b,int &c,int &d){
        int x0=a,x1=b,x2=c;
        a=x0,b=x2-d,c=x1-x0-x2+d;
}
inline void FWT(int *a,int lim){
        for(R int mid=1;mid<lim;mid<<=2)
                for(R int j=0;j<lim;j+=(mid<<2))
                        fp(k,0,mid-1)
                        FWT(a[j+k],a[j+k+mid],a[j+k+mid*2],a[j+k+mid*3]);
}
inline void IFWT(int *a,int lim){
        for(R int mid=1;mid<lim;mid<<=2)
                for(R int j=0;j<lim;j+=(mid<<2))
                        fp(k,0,mid-1)
                        IFWT(a[j+k],a[j+k+mid],a[j+k+mid*2],a[j+k+mid*3]);
}

我们发现二进制的三个卷积也可以用这个套路来解释

暂时还凑不出三进制循环卷积的系数，所以只会用扩域的那个方法了

如果有哪位老鸽能凑出来的话可以在下方尽情嘲讽我