UOJ#310. 【UNR #2】黎明前的巧克力(FWT)

题意

sol

然鹅我最后一步还是没看懂qwq。。

坐等sovietpower大佬发博客

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 23) + 10, mod = 998244353, inv2 = (mod + 1) / 2, inv4 = 748683265, lim = 1048576;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[maxn], po3[maxn];
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
void fwt(int *a, int opt) {
    for(int mid = 1; mid < lim; mid <<= 1) 
        for(int r = mid << 1, j = 0; j < lim; j += r)
            for(int k = 0; k < mid; k++) {
                int x = a[j + k], y = a[j + k + mid];
                if(opt == 1) a[j + k] = add(x, y), a[j + k + mid] = add(x, -y);
                else a[j + k] = mul(add(x, y), inv2), a[j + k + mid] = mul(add(x, -y), inv2);               
            }
}
int main() {
    n = read();
    for(int i = 1; i <= n; i++) a[read()]++;
    fwt(a, 1);
    po3[0] = 1;
    for(int i = 1; i <= n; i++) po3[i] = mul(3, po3[i - 1]);
    for(int i = 0; i < lim; i++) {
        a[i] = add(mul(2, a[i]), n);
        int c3 = mul(add(a[i], n), inv4);
        a[i] = po3[c3];
        if((n - c3) & 1) a[i] = mod - a[i];
    }
    fwt(a, -1);
    cout << (a[0] - 1 + mod) % mod;
    return 0;
}