FWT_xor
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/b12d86c535e397db9b86b6bed1b3712b" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/81be4c6c658ed4c6b7220e918ee392ed" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/1b1df424766f52be0bb6bbe6b73dd7b9" alt="" /></p>
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 100005, mod = 998244353;
ll A[maxn], b[maxn];//注意从下标为0开始存值
void FWT_xor(ll *a, int n, int opt = 1){
ll inv2 = qpow(2, mod-2);
for(int i = 1; i < n; i <<= 1){
for(int p = i << 1, j = 0; j < n; j += p){
for(int k = 0; k < i; ++k){
ll X = a[j+k], Y = a[i+j+k];
a[j+k] = (X+Y) % mod; a[i+j+k] = (X+mod-Y) % mod;
if(opt == -1){
a[j+k] = 1ll * a[j+k] * inv2 % mod;
a[i+j+k] = 1ll * a[i+j+k] * inv2 % mod;
}
}
}
}
}
int main(){
int n, tn = 1; scanf("%d", &n);
//将最长的那个多项式的次数n进行变换得到tn
while(tn < 2 * n + 1) tn <<= 1;
FWT_xor(A, tn), FWT_xor(B, tn);
for(int i = 0; i < tn; i++) A[i] = A[i] * B[i] % mod;
FWT_xor(A, tn, -1);
return 0;
}</code></pre>