枚举两个人选的卡的并集 \(S\)，那么当 \(\bigoplus\limits_{i \in S} a_i = 0\) 时 \(S\) 有贡献 \(2^{|S|}\)。
考虑将 \(2^{|S|}\) 分摊到每个元素上，也就是每个元素有 \(2\) 的贡献，然后把这些贡献乘起来。所以题目其实是想让我们算这个东西：\([x^0] \prod\limits_{i = 1}^n (1 + 2x^{a_i})\)，定义 \(x^i \times x^j = x^{i \oplus j}\)。
令 \(F_i(x) = 1 + 2x^{a_i}\)，考虑给每个 \(F_i\) FWT 一下，对位乘后再逆 FWT 回去。因此我们已经有了一个 \(O(nV)\) 的做法，显然不能通过。
考虑 \(F_i\) FWT 后的结果，因为此处 \(\text{FWT}(a)_i = \sum\limits_{j} (-1)^{\text{popcount}(i \& j)} a_j\)，容易发现 \(\text{FWT}(F_i)\) 只含有 \(1\) 或 \(-3\)。因此我们对位乘后第 \(i\) 位的结果可以表示成 \((-1)^{x_i} 3^{n - x_i}\)。
令 \(G = \text{FWT}(F_1) + \text{FWT}(F_2) + \cdots + \text{FWT}(F_n)\)，那么我们有 \(-x_i + 3(n - x_i) = G_i\)。解得 \(x_i = \frac{3n - G_i}{4}\)。又因为 FWT 的线性性我们有 \(G = \text{FWT}(F_1 + F_2 + \cdots F_n)\)，所以 \(G_i\) 和 \(x_i\) 都能快速求出来。所以我们求出这样对位乘后第 \(i\) 位的结果，最后再逆 FWT 回去即可得到 \([x^0] \prod\limits_{i = 1}^n F_i\)。
总时间复杂度 \(O(n \log V)\)。
code
// Problem: K. Deck-Building Game
// Contest: Codeforces - 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
// URL: https://codeforces.com/problemset/problem/1906/K
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 131100;
const int N = 131072;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, a[maxn];
inline void FWT(ll *a, ll o) {
for (int k = 1; k < N; k <<= 1) {
for (int i = 0; i < N; i += (k << 1)) {
for (int j = 0; j < k; ++j) {
ll x = a[i + j], y = a[i + j + k];
a[i + j] = (x + y) * o % mod;
a[i + j + k] = (x - y + mod) * o % mod;
}
}
}
}
void solve() {
scanf("%lld", &n);
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
a[x] += 2;
}
a[0] += n;
FWT(a, 1);
ll inv4 = qpow(4, mod - 2);
for (int i = 0; i < N; ++i) {
ll x = (n * 3 - a[i] + mod) * inv4 % mod;
a[i] = ((x & 1) ? mod - 1 : 1) * qpow(3, n - x) % mod;
}
FWT(a, inv2);
printf("%lld\n", a[0]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}