Codeforces Global Round 2 H - Triples
https://codeforces.com/contest/1119/problem/H
Preliminaries
Hadamard transform of 3bits is almost the same as Fourier transform of 2*2*2.
A polynomial of x,y,z can be represented as 8 coefficients of 1,x,y,z,xy,xz,yz,xyz. Hadamard transform is equavalent to finding 8 values, f(1,1,1),f(1,1,-1),f(1,-1,1),f(1,-1,-1),f(-1,1,1),f(-1,1,-1),f(-1,-1,1),f(-1,-1,-1). We write \(x^{0101}=x_0x_2\), \(x^{1101}=x_0x_2x_3\). We define \(x^{0101} x^{1101} = x^{0101 \oplus 1101}\). In other words, \(x_i^2=1\). If we give such a property to indeterminants, we can say that this is a polynomial ring \(R[x_0,\ldots,x_{K - 1}]\).
Solution
Inputs are denoted by capital letters. Using polynomials, this problem can be restated as finding the coefficient of each monomial of
\[ \prod_{i} (X x^{A[i]} + Y x^{B[i]} + Z x^{C[i]}) \]
Move all \(x^{A[i]}\) to outside, then it becomes
\[ x^{\bigoplus_i A[i]} \prod_i (X + Y x^{A[i] \oplus B[i]} + Z x^{A[i] \oplus C[i]})\]
Later, let \(B[i] \gets A[i] \oplus B[i]\), \(C[i] \gets A[i] \oplus C[i]\). Then, this problem can be reduced to the problem expanding the below.
\[ \prod_i (X + Y x^{B[i]} + Z x^{C[i]})\]
First, we apply Hadamard transform to the above polynomial. For any assignment of x, each factor takes only four values, X+Y+Z,X-Y+Z,X+Y-Z,X-Y-Z. Fix an assignment of \(x\), let \(\alpha, \beta, \gamma, \delta\) be the numbers of X+Y+Z, X-Y+Z, X+Y-Z, X-Y-Z, respectively. The following holds.
\begin{align}
\alpha + \beta + \gamma + \delta &= N,\\
\alpha - \beta + \gamma - \delta &=\sum_i x^{B[i]},\\
\alpha + \beta - \gamma - \delta &=\sum_i x^{C[i]},\\
\alpha - \beta - \gamma + \delta &=\sum_i x^{B[i] \oplus C[i]}.
\end{align}
Thus we can obtain \(\alpha, \beta, \gamma, \delta\) by solving this equations.
#include <stdio.h> #include <vector> using namespace std; const int MOD = 998244353; struct mint { int n; mint(int n_ = 0) : n(n_) {} }; mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; } mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; } mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; } mint &operator+=(mint &a, mint b) { return a = a + b; } mint &operator-=(mint &a, mint b) { return a = a - b; } mint &operator*=(mint &a, mint b) { return a = a * b; } mint modpow(mint a, long long b) { mint res = 1; while (b > 0) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } mint modinv(mint a) { return modpow(a, MOD - 2); } mint operator/(mint a, mint b) { return a * modinv(b); } template<class T> void H(T *a, int l, int r) { if (r - l == 1) return; int n = r - l; int m = (l + r) / 2; H(a, l, m); H(a, m, r); for (int i = l; i < m; i++) { int j = i + n / 2; T x = a[i]; T y = a[j]; a[i] = x + y; a[j] = x - y; } } mint in() { int x; scanf("%d", &x); return x % MOD; } int main() { int N, K; scanf("%d %d", &N, &K); vector<int> A(1 << K); vector<int> B(1 << K); vector<int> C(1 << K); mint x = in(), y = in(), z = in(); int s = 0; for (int i = 0; i < N; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); s ^= a; b ^= a; c ^= a; A[b]++; B[c]++; C[b^c]++; } H(A.data(), 0, 1<<K); H(B.data(), 0, 1<<K); H(C.data(), 0, 1<<K); vector<mint> ans(1 << K, 1); for (int i = 0; i < 1 << K; i++) { // x+y+z -> a // x-y+z -> b // x+y-z -> c // x-y-z -> d vector<int> D(4); // D[0] = a + b + c + d // D[1] = a - b + c - d // D[2] = a + b - c - d // D[3] = a - b - c + d D[0] = N; D[1] = A[i]; D[2] = B[i]; D[3] = C[i]; H(D.data(), 0, 4); mint v = 1; v *= modpow(x+y+z, D[0] / 4); v *= modpow(x-y+z, D[1] / 4); v *= modpow(x+y-z, D[2] / 4); v *= modpow(x-y-z, D[3] / 4); ans[i] = v; } H(ans.data(), 0, 1 << K); vector<mint> out(1 << K); for (int i = 0; i < 1 << K; i++) { out[i ^ s] = ans[i] / (1 << K); } for (int i = 0; i < 1 << K; i++) { printf("%d ", out[i].n); } putchar('\n'); }