很牛啊！感觉官方题解讲的基本挺详细且直观的。感觉如果做过三进制 mex 卷积那个题 qoj12334 或者 qoj9562 会更好理解。
题意：只用乘法，加法，减法，完成异或卷积，要求复杂度 \(O(n^22^n)\)。同时注意这个乘法运算是不满足交换律的，同时模数不保证是奇数。
做法：
思考我们现在直接做异或卷积错在哪里了，我们发现我们 ifwt 的时候需要 \(2\) 的逆元所以爆炸了。但是我们发现其他的卷积都不需要逆元。
如果你做过三进制 mex 卷积，你会知道我们可以对每个位分别卷积，讨论每个位，我们分别计算 \((a_0,a_1),(b_0,b_1)\) 也就是这一位是 \(0,1\) 的一个卷积的情况，是几个多项式，我们分别计算 \(f_i = \sum\limits_{x+y=i}a_xb_y\) 对位相乘的情况即可，可以做到一个 \(3^n\) 的做法。但是不够快。
我们考虑这个东西更本质的一个描述，我们假设现在的多项式是 \(a_0+a_1X\)，\(X\) 这里就作为一个占位符区分 \(0,1\) 的位置。那么我们考虑两个多项式卷起来，我们异或卷积的目标是 \((a_0b_0+a_1b_1)+(a_0b_1+a_1b_0)X\)，但是直接乘法会有一个 \(a_1b_1X^2\)，这意味着我们需要 \(X^2=1\) 才行，解得 \(X=\pm 1\)，也就是函数 \(f(X)=X^2-1\) 的零点，然后我们把 \(X=\pm 1\) 带入插值，我们就可以分别得到这两个东西的和和差，就可以算出来这两个东西的值，只不过仍然需要除以 \(2\)。
我们也可以写一些其他的卷积，但是跟本题做法关系没那么大，比如或卷积，他就要求 \(X^2=X\)，也就是 \(f(X)=X^2-X\)，解得 \(X=0/1\)，所以我们带这个进去插值就可以得到想要的结果。
我们在 \(\bmod 2\) 的视角下去观察这个东西，发现解得 \(X=1\)，这很完蛋，因为我们只有一个点显然不足够插值，但是我们发现一个事情，子集卷积要求 \(a_1b_1\) 的系数是 \(0\)，也就是 \(X^2=0\)，在 \(\bmod 2\) 意义下，我们只需要做一个平移，异或卷积和子集卷积就是等价的，所以我们现在解决的问题是可以类比子集卷积的解决方式的。
那么我们回归原问题，我们同样考虑去平移一下，我们把 \(f(X)=X^2-1=(X+1)(X-1)\) 平移成 \(f(X)=X(X-2)\)。怎么平移呢，我们写一写柿子 \(a_0+a_1(X-1)\to a'_0+a'_1X\)，那么就让 \(a'_0=a_0-a_1,a'_1=a_1\) 即可，然后我们去算 \(f(X)=X(X-2)\) 的即可，这个我们可以写开一下，发现就是对于两个同时这一位为 \(1\) 的会多一个 \(2\) 的贡献，所以算出来的会是 \(c_{x\cup y}\sum a_x b_y2^{|x\cap y|}\)，这个东西直接按照子集卷积做，然后把 \(|x\cap y|\) 改成 \(|x|+|y|-|x\cup y|\) 即可，就只用改改子集卷积就可以了，最后再平移回去。复杂度 \(O(n^22^n)\)。
感觉很多东西有点抽象，没讲清楚的地方谢罪了 /kel
代码：
#include <bits/stdc++.h>
using namespace std;
#include "xor.h"
const int maxn = (1 << 20) + 5, mod = 998244353, inv = (mod + 1) / 2;
int n, m, cnt[maxn];
vector<mat> f[21], g[41], c;
vector<mat> xor_convolution(vector<mat> a, vector<mat> b, int subtask_id) {n = a.size();while((1 << m) < n)m++;for (int h = 2; h <= n; h <<= 1)for (int i = 0; i < n; i += h)for (int j = i; j < i + h / 2; j++)a[j] -= a[j + h / 2];for (int h = 2; h <= n; h <<= 1)for (int i = 0; i < n; i += h)for (int j = i; j < i + h / 2; j++)b[j] -= b[j + h / 2];for (int i = 1; i < n; i++)cnt[i] = cnt[i >> 1] + (i & 1);for (int i = 0; i <= m; i++)f[i].resize(n);for (int j = 0; j <= 2 * m; j++)g[j].resize(n);c.resize(n);for (int i = 0; i < n; i++)f[cnt[i]][i] = a[i], g[cnt[i]][i] = b[i];for (int t = 0; t <= m; t++) {for (int h = 2; h <= n; h <<= 1)for (int i = 0; i < n; i += h)for (int j = i; j < i + h / 2; j++)f[t][j + h / 2] += f[t][j], g[t][j + h / 2] += g[t][j];}for (int i = 0; i < n; i++) {vector<mat> v1, v2; v1.resize(m + 1), v2.resize(m + 1);for (int j = 0; j <= m; j++)v1[j] = f[j][i], v2[j] = g[j][i];v1 = convolution(v1, v2);for (int j = 0; j <= 2 * m; j++)g[j][i] = v1[j];}for (int t = 0; t <= 2 * m; t++) {for (int h = 2; h <= n; h <<= 1)for (int i = 0; i < n; i += h)for (int j = i; j < i + h / 2; j++)g[t][j + h / 2] -= g[t][j];}for (int i = 0; i < n; i++) {for (int j = 2 * m; j >= cnt[i]; j--)c[i] = c[i] + c[i] + g[j][i];}for (int h = 2; h <= n; h <<= 1)for (int i = 0; i < n; i += h)for (int j = i; j < i + h / 2; j++)c[j] += c[j + h / 2];return c;
}