fwt.cpp

void FWT_or(int *a, int opt)
{
	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)
				if (opt == 1)a[i + j + k] = (a[j + k] + a[i + j + k]) % MOD;
				else a[i + j + k] = (a[i + j + k] + MOD - a[j + k]) % MOD;
}
void FWT_and(int *a, int opt)
{
	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)
				if (opt == 1)a[j + k] = (a[j + k] + a[i + j + k]) % MOD;
				else a[j + k] = (a[j + k] + MOD - a[i + j + k]) % MOD;
}
void FWT_xor(int *a, int opt)
{
	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)
			{
				int 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;
			}
}
//下标从0开始 1 正 -1 逆
//3 3 7 7 7 7 7 2 2 2 2 2 2 10 11 13== 3 3 3 3 3 ==15 15