「UNR#2」黎明前的巧克力

解题思路

考虑一个子集 \(S\) 的异或和如果为 \(0\) 那么贡献为 \(2^{|S|}\) ，不难列出生产函数的式子，这里的卷积是异或卷积。

因为每一项只有两项 \(x^0,x^{a_i}\) 有值，记 \(f_i(x) =2x^{a_i}+1\), \(f'_i(x)=\text{Fwt}f(x)\) ，有

不难发现 \(f'_i(x)\) 的每一项不是 \(3\) 就是 \(-1\) 。

这一步比较巧妙，考虑到 \(\text{Fwt}\) 是一个线性变换，线性变换的和等于和的线性变换，我们对所有多项式求和后 \(\text{Fwt}\) ，可以解方程解出每一项由多少个 \(3\) 和多少个 \(-1\) 构成。

设 \([x^S]f_i(x)\) 由 \(k\) 个 \(-1\) 贡献得到 \(k =\frac{3n-[x^S]f_i(x)}{4}\)，然后我们要求所有多项式卷积的 \(\text{Fwt}\) 后的结果，即 \([x^S]=(-1)^k\times3^{n-k}\) ，最后再 \(\text{IFwt}\) 回去即可。

其实最后是不需要 \(\text{IFwt}\) 的，我们只需要求 \([x^0]F(x)\) 的值，根据 \(\text{IFwt}\) 的式子

所以 \([x^0]F(x)\) 的值就是每一项系数加起来除一个 \(2^n\) 。

小结 ：遇到点值的时候不要只考虑套路，应当多观察性质。

code

/*program by mangoyang*/

#include <bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef unsigned long long ull;

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int ch = 0, f = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

const int N = 2000005, mod = 998244353;

int a[N], n, res;

inline int Pow(int a, int b){

	int ans = 1;

	for(; b; b >>= 1, a = 1ll * a * a % mod)

		if(b & 1) ans = 1ll * ans * a % mod;

	return ans;

}

int main(){

	read(n);

	int tot = 20, len = 1 << 20;

	for(int i = 1, x; i <= n; i++)

		read(x), a[x] += 2, a[0]++;

	for(int i = 0; i < tot; i++)

		for(int s = 0; s < len; s++) if(s & (1 << i)){

			int x = a[s], y = a[s^(1<<i)];

			a[s^(1<<i)] = x + y >= mod ? x + y - mod : x + y;

			a[s] = y - x < 0 ? y - x + mod : y - x;;

		}

	for(int i = 0; i < len; i++){

		int k = ((3ll * n - a[i]) % mod + mod) % mod;

		k = 1ll * k * Pow(4, mod - 2) % mod;

		if(k & 1) res -= Pow(3, n - k);

			else res += Pow(3, n - k);

		if(res >= mod) res -= mod;

		if(res < 0) res += mod;

	}

	cout << (1ll * res * Pow(len, mod - 2) % mod + mod - 1) % mod << endl;

	return 0;

}