CF1119H Triple 题解

Description

SK 酱送给你了一份生日礼物。礼物是 $n$ 个三元组 $(a_i,b_i,c_i)$ 和四个正整数 $x,y,z,k$。

你利用这 $n$ 个三元组填充了 $n$ 个数组，其中第 $i$ 个数组中有 $x$ 个 $a_i$，$y$ 个 $b_i$，$z$ 个 $c_i$（所以第 $i$ 个数组长度为 $(x+y+z)$。

对于 $i=0,1,\cdots,2^k-1$，回答以下询问：

• 从每个数组中选择恰好一个数，使得这些数的 $\mathrm{xor}$ 和为 $i$，方案数是多少？

你只需要输出方案数对 $998,244,353$ 取模后得到的结果。

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^5$，$1\le k\le 17$；
• $0\le x,y,z\le 10^9$；
• $0\le a_i,b_i,c_i\lt 2^k$。

Solution

首先先让 $b_i$ 和 $c_i$ 都异或上 $a_i$，这样就转化为了 $a_i$ 等于 $0$ 的情况。

容易发现这是个 FWT 的形式，设 $cnt(i)=popcount(i)$，$FWT_k[i]$ 表示 $(a_k,b_k,c_k)$ 的 FWT 数组，那么 $FWT_k[i]=(-1)^{cnt(i\&a_k)}x+(-1)^{cnt(i\&b_k)}y+(-1)^{cnt(i\&c_k)}z$。

由于 $a_k=0$，所以第一项为 $x$，即 $FWT_k[i]=x+(-1)^{cnt(i\&b_k)}y+(-1)^{cnt(i\&c_k)}z$。

这里的 $FWT_k[i]$ 只有 $4$ 种可能，分别是 $x+y+z,x+y-z,x-y+z,x-y-z$，设这四种分别出现了 $c_1,c_2,c_3,c_4$ 次。考虑用解方程的方式解出这四个数。

第一个式子是 $c_1+c_2+c_3+c_4=n$。

先设 $f_{1,k}[i]=(-1)^{cnt(i\&b_k)}$，则 $c_1+c_2-c_3-c_4=\sum_{k=1}^{n}{f_{1,k}[i]}$。

同理设 $f_{2,k}[i]=(-1)^{cnt(i\&c_k)}$，则 $c_1-c_2+c_3-c_4=\sum_{k=1}^{n}{f_{2,k}[i]}$。

然后设 $f_{3,k}[i]=(-1)^{cnt(i\&b_k)+cnt(i\&c_k)}$，则 $c_1-c_2-c_3+c_4=\sum_{k=1}^{n}{f_{3,k}[i]}$。

可以用 FWT 分别求出 $f_{1,k}[i],f_{2,k}[i],f_{3,k}[i]$ 的和，乘起来后再 FWT 回去就是答案。

时间复杂度：$O(n+2^kk)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5, kMaxS = (1 << 17), kMod = 998244353, kInv2 = (kMod + 1) / 2;

int n, k, x, y, z, sum;
int a[kMaxN], b[kMaxN], c[kMaxN];
int f[kMaxS], f1[kMaxS], f2[kMaxS], f3[kMaxS];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int fix(int x) { return (x % kMod + kMod) % kMod; }
inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void FWT(int *a, int n) {
  for (int len = 2; len <= n; len <<= 1) {
    int m = len / 2;
    for (int i = 0; i < n; i += len) {
      for (int j = i; j < i + m; ++j) {
        int tmp = a[j];
        a[j] = add(a[j], a[j + m]);
        a[j + m] = sub(tmp, a[j + m]);
      }
    }
  }
}

void IFWT(int *a, int n) {
  for (int len = 2; len <= n; len <<= 1) {
    int m = len / 2;
    for (int i = 0; i < n; i += len) {
      for (int j = i; j < i + m; ++j) {
        int tmp = a[j];
        a[j] = 1ll * kInv2 * add(a[j], a[j + m]) % kMod;
        a[j + m] = 1ll * kInv2 * sub(tmp, a[j + m]) % kMod;
      }
    }
  }
}

void dickdreamer() {
  std::cin >> n >> k >> x >> y >> z;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i] >> b[i] >> c[i];
    sum ^= a[i], b[i] ^= a[i], c[i] ^= a[i];
    ++f1[b[i]], ++f2[c[i]], ++f3[b[i] ^ c[i]];
  }
  FWT(f1, (1 << k)), FWT(f2, (1 << k)), FWT(f3, (1 << k));
  for (int i = 0; i < (1 << k); ++i) {
    int c1, c2, c3, c4;
    c1 = fix(n + f1[i] + f2[i] + f3[i]) / 4;
    c2 = fix(n + f1[i] - f2[i] - f3[i]) / 4;
    c3 = fix(n - f1[i] + f2[i] - f3[i]) / 4;
    c4 = fix(n - f1[i] - f2[i] + f3[i]) / 4;
    f[i] = 1;
    f[i] = 1ll * f[i] * qpow(fix(x + y + z), c1) % kMod;
    f[i] = 1ll * f[i] * qpow(fix(x + y - z), c2) % kMod;
    f[i] = 1ll * f[i] * qpow(fix(x - y + z), c3) % kMod;
    f[i] = 1ll * f[i] * qpow(fix(x - y - z), c4) % kMod;
  }
  IFWT(f, (1 << k));
  for (int i = 0; i < (1 << k); ++i) std::cout << f[i ^ sum] << ' ';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}