UOJ310 黎明前的巧克力(fwt)

题目大意

求 \(\sum_{xor(S)=0}2^{|S|}\)，还是去看原题吧

解题思路

考虑其生成函数
\[ \prod (1+2x^{a_i}) \]
最后答案就是 \(x^0\) 的系数

发现对于 \((1+2x^{a_i})\) 做 fwt 的系数只有 -1，3

也就是我们求出最终的点值是由一些 -1 和 3 乘起来的，我们只要知道分别的个数即可，那么有个小技巧，我们直接把它们加起来做 fwt 知道点值的和，通过鸡兔同笼就能直接算出来个数了

代码

#include 
#include 
#include 
#include 
#include 
#include 
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template 
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template
inline void write(F x, char ed = '\n')
{
    static short st[30];short tp=0;
    if(x<0) putchar('-'),x=-x;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar('0'|st[tp--]);
    putchar(ed);
}

template 
inline void Mx(T &x, T y) { x < y && (x = y); }

template 
inline void Mn(T &x, T y) { x > y && (x = y); }

const int P = 998244353;
const int inv2 = (P + 1) / 2;
const int N = 2000005;
int m, n; ll f[N], ans;
void fwt_xor(ll *a, int ty) {
    for (int i = 1;i < m; i <<= 1) 
        for (int j = 0;j < m; j += (i << 1)) 
            for (int k = 0;k < i; k++) {
                ll x = a[j+k], y = a[i+j+k];
                a[j+k] = (x + y) % P;
                a[i+j+k] = (x - y) % P;
            }
}

ll fpw(ll x, ll mi) {
    ll res = 1;
    for (; mi; mi >>= 1, x = x * x % P)
        if (mi & 1) res = res * x % P;
    return res;
}

int main() {
    read(n); 
    for (int i = 1, x;i <= n; i++) 
        read(x), f[0]++, f[x] += 2;
    m = 1 << 20, fwt_xor(f, 1);
    for (int i = 0;i < m; i++) {
        int k = (3 * n - f[i]) / 4;
        f[i] = fpw(3, n - k);
        if (k & 1) f[i] = P - f[i];
        ans += f[i]; ans >= P && (ans -= P);
    }
    write((ans * fpw(m, P - 2) % P + P - 1) % P);
    return 0;
}