你的生日礼物是(n)个整数三元组。第(i)个三元组是({a_i,b_i,c_i}),所有数字(j)都满足(0le j<2^k),(k)是一个固定的数字，将由题目输入。
一天，你玩三元组玩腻了，所以你有了3个新的整数(x,y,z),然后填充了(n)个数组。第(i)个数组有(x)个(a_i),(y)个(b_i),(z)个(c_i).这样，每个数组的大小都是(x+y+z).
你希望从每个数组里选择1个整数，使得它们的xor(按位异或)值恰好为(t). 对于区间([0,2^k-1])内的每个数字(t),输出满足上面的条件的方案数 模 (998244353)
输入:
第一行读入(n,k),第二行读入(x,y,z),接下来读入(n)行。第(i)行读入(a_i),(b_i),(c_i)。
输出：
一行(2^k)个整数,用空格分隔。第(i)个数字是从每个数组里选一个整数使它们的xor值等于(t=i-1)的方案数模(998244353)
(1 leq n leq 10^{5},1 leq k leq 17,0 leq x,y,z leq 10^{9},0 leq a_{i} , b_{i} , c_{i} leq 2^{k} - 1)
考虑暴力做法，整出来 (n) 个多项式 ，(F_i[a_i]=x,F_i[b_i]=y,F_i[c_i]=z) ，然后 FWT 过去再 IFWT 回来就能算出来答案，这样子复杂度是 (O(kn2^k)) 。
然后优化，写出来第 (t) 项的式子：
因为异或卷积的 (c(i,j)=(-1)^{num(i&j)}) ， (num) 是二进制下 (1) 的个数.
于是就有：
这样子 (x+y+z) 的情况有 (8) 种，考虑减少情况，对每一个三元组都异或上 (a_i) ，那么三元组就变成了 ({0,b_ioplus a_i,c_ioplus a_i}) 。
这样子 ((-1)^{num(i&0)}=1) ，那么情况就变成了四种：
考虑分别对这个系数贡献了 (s_1,s_2,s_3,s_4) 次，那么我们一定会有这个方程：
然后考虑赋 (x=0,y=1,z=0) ，那么 (F'_t[i]=sum_{j=1}^n(-1)^{num(i&b_t)}) ，只需要看 (y) 的正负号，相当于数 (s_1+s_2-s_3-s_4) ，设 (=B) 。
同理赋 (x=0,y=0,z=1) ，那么就有 (s_1-s_2+s_3-s_4=C) 。
然后把这两个多项式卷起来，就相当于对 (F[b_ioplus c_i]) FWT ，这样就看 (y) 和 (z) 的正负号，得到 (s_1-s_2-s_3+s_4=BC) 。
于是就可以解方程了，最后可以解得：
然后算出来 (F') IFWT 回去就可以了。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e5;
const int M = 17;
const int p = 998244353;
using namespace std;
int n,k,x,y,z,a[N + 5],b[N + 5],c[N + 5],A[1 << M],B[1 << M],C[1 << M],D[1 << M],sa;
int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % p : 0,a = 1ll * a * a % p,x >>= 1);return s;}
void FWT(int *a)
{
for (int i = 1;i < (1 << k);i <<= 1)
for (int j = 0;j < (1 << k);j += i << 1)
for (int k = 0;k < i;k++)
{
int a0 = a[j + k],a1 = a[j + k + i];
a[j + k] = (a0 - a1) % p;
a[j + k + i] = (a0 + a1) % p;
}
}
void IFWT(int *a)
{
int inv = mypow(2,p - 2);
for (int i = 1;i < (1 << k);i <<= 1)
for (int j = 0;j < (1 << k);j += i << 1)
for (int k = 0;k < i;k++)
{
int a0 = 1ll * a[j + k] * inv % p,a1 = 1ll * a[j + k + i] * inv % p;
a[j + k] = (a0 + a1) % p;
a[j + k + i] = (-a0 + a1) % p;
}
}
int main()
{
scanf("%d%d",&n,&k);
scanf("%d%d%d",&x,&y,&z);
for (int i = 1;i <= n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
b[i] ^= a[i];
c[i] ^= a[i];
sa ^= a[i];
}
for (int i = 1;i <= n;i++)
B[b[i]]++,C[c[i]]++,D[b[i] ^ c[i]]++;
FWT(B);FWT(C);FWT(D);
int inv = mypow(4,p - 2);
int x1 = (0ll + x + y + z) % p,x2 = (0ll + x + y - z) % p,x3 = (0ll + x - y + z) % p,x4 = (0ll + x - y - z) % p;
for (int i = 0;i < (1 << k);i++)
{
int S1 = ((0ll + n + B[i] + C[i] + D[i]) % p * inv % p + p) % p;
int S2 = ((0ll + n + B[i] - C[i] - D[i]) % p * inv % p + p) % p;
int S3 = ((0ll + n - B[i] + C[i] - D[i]) % p * inv % p + p) % p;
int S4 = ((0ll + n - B[i] - C[i] + D[i]) % p * inv % p + p) % p;
A[i] = 1ll * mypow(x1,S1) * mypow(x2,S2) % p * mypow(x3,S3) % p * mypow(x4,S4) % p;
}
IFWT(A);
for (int i = 0;i < (1 << k);i++)
printf("%d ",(A[i ^ sa] + p) % p);
return 0;
}