Triple

Title Link: luogu CF1119H

General idea of the topic

Here are n arrays. Each array has n numbers, including x ai, y bi, and z ci.
x. Y and Z are the same for each array, while AI, Bi and CI are different for each array.
Then I ask you to select a number from each array for each I, and how many cases are there when their XOR and sum are i.

thinking

Consider making a generating function similar to each array

\(u\) pieces \ (a_i\), \ (v\) pieces \ (b_i\), \ (w\) pieces \ (c_i\)
\(ux^{a_i}+vx^{b_i}+wx^{c_i}\)

Then the answer is the array they multiply (FWT XOR multiply).
But we can't multiply them one by one. Let's add them up, multiply them, and then solve the equations with the two countries to get the real number of each case, and then get the real value.

Then, because there are \ (8\) cases, we will consider a little simplification. The size of the \ (i\) array is exclusive or (a_i\), and then there is only \ (4\), and the position of the answer is exclusive or the exclusive or sum of all \ (a_i\).
\(a_i\rightarrow 1,b_i\rightarrow b_i\oplus a_i,c_i\rightarrow \oplus a_i\)
\(u+vx^{b_i}+wx^{c_i}\)

One location \ (i\), four possibilities:
\(u+v+w\) number \ (n\u 1\)
\(u+v-w\) number \ (n\u 2\)
\(u-v+w\) number \ (n\u 3\)
\(u-v-w\) number \ (n\u 4\)

Then let's consider whether we can solve the four equations in some way.
First of all, the first formula is obviously the sum of four \ (n_i\) is \ (n\).
Let's consider only looking at the positive and negative of \ (v\) (that is, no matter what \ (u,w\) is, or as \ (0\))
This is an ordinary FWT, and you can get \ (y\u 1\).
Similarly, if we only look at the positive and negative of \ (w\), we can get \ (y_2\).

We still need one. Let's consider whether \ (v,w\) can make a contribution at the same time.
That is, the position of \ (b_i\oplus c_i\) is \ (1\), and the other positions are \ (0\), which is actually the convolution of the above two formulas.
Then you can get a \ (y_3\) by doing this, and that formula is complete.

\(\begin{cases}n_1+n_2+n_3+n_4=n\\ n_1+n_2-n_3-n_4=y_1\\ n_1-n_2+n_3-n_4=y_2\\ n_1-n_2-n_3+n_4=y_3\end{cases}\)

\(\begin{cases}n_1=(n+y_1+y_2+y_3)/4\\n_2=(n+y_1-2n_1)/2\\n_3=(n+y_2-2n_1)/2\\n_4=(n+y_3-2n_1)/2\end{cases}\)

Then this problem can be done. It is not difficult to see that there is a model for this problem.
That is, you can do FWT once through the contribution of each position to get the constant term of the equation (there are \ (2^k\) in total, which corresponds to \ (2^k\) possibilities). Then you can eliminate the equation or solve the equation by yourself, and then take it back. IFWT.

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 998244353

using namespace std;

const int N = (1 << 17);
int n, k, all;
ll f[N], f1[N], f2[N], f3[N], u, v, w;

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo; x = x * x % mo; y >>= 1;
	}
	return re;
}

void FWT(ll *f, ll op, int n) {
	for (int mid = 1; mid < n; mid <<= 1)
		for (int R = mid << 1, j = 0; j < n; j += R)
			for (int k = 0; k < mid; k++) {
				ll x = f[j | k], y = f[j | mid | k];
				f[j | k] = (x + y) % mo * op % mo;
				f[j | mid | k] = (x - y + mo) % mo * op % mo;
			}
}

int main() {
	scanf("%d %d", &n, &k);
	scanf("%lld %lld %lld", &u, &v, &w);
	for (int i = 1; i <= n; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		b ^= a; c ^= a; all ^= a;
		f1[b]++; f2[c]++; f3[b ^ c]++;
	}
	
	FWT(f1, 1, 1 << k); FWT(f2, 1, 1 << k); FWT(f3, 1, 1 << k);
	ll inv4 = ksm(4, mo - 2), inv2 = ksm(2, mo - 2);
	for (int i = 0; i < 1 << k; i++) {
		ll n1 = (n + f1[i] + f2[i] + f3[i]) % mo * inv4 % mo;
		ll n2 = (n + f1[i] - 2 * n1 + 2 * mo) % mo * inv2 % mo;
		ll n3 = (n + f2[i] - 2 * n1 + 2 * mo) % mo * inv2 % mo;
		ll n4 = (n + f3[i] - 2 * n1 + 2 * mo) % mo * inv2 % mo;
		f[i] = ksm((u + v + w) % mo, n1) * ksm((u + v - w + mo) % mo, n2) % mo
		* ksm((u - v + w + mo) % mo, n3) % mo * ksm((u - v - w + 2 * mo) % mo, n4) % mo;
	}
	FWT(f, (mo + 1) / 2, 1 << k);
	for (int i = 0; i < 1 << k; i++) printf("%lld ", f[i ^ all]);
	
	return 0;
}