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

解题思路

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

[[x^0]prod_{i=1}^{n} (2x^{a_i}+1) ]

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

[f_i'(x)=sum_{S} (1+2 imes(-1)^{|Scap a_i|})x^S ]

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

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

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

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

[F_S=dfrac{1}{2^n}sum_{T}(-1)^{|Scap T|}F'_T ]

所以 ([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;
}