UOJ310【UNR #2】黎明前的巧克力

Description

$\rm Link$

Solution

假设 $\rm Evan$ 选择的是集合 $S$ ，$\rm Lyra$ 选择的是集合 $T$ 。
观察到条件：

$\bigoplus_{i=1}^{n}[i\in S]a_i=\bigoplus_{i=1}^{n}[i\in T]a_i$

以及

$S\cap T =\emptyset$

我们考虑枚举 $S\cup T$，因为 $S\cup T$ 的元素异或和为 $0$，并且每找到一个元素异或和为 $0$ 的非空集合 $\mathcal{Q}$ ，我们有 $2^{|\mathcal{Q}|}$ 种方法拆分它为 $S$ 和 $T$ 。
构造集合幂级数，考虑每个元素选与不选，则问题转化为求下式的值

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

异或卷积自然考虑用 $\rm FWT$ 做一做。

$[x^{\{\emptyset\}}]\text{IFWT}(\prod_{i=1}^{n}\text{FWT}(2x^{\{a_i\}}+x^{\{\emptyset\}}))$

里面相当于要做 $n$ 次 $\rm FWT$ ，复杂度有点离谱。
考虑一个奇怪的事情：事实上，我们每次都只对一个形如 $2x^{\{v\}}+x^{\{\emptyset}\}$ 的形式幂级数做 $\rm FWT$。我们考虑 $n$ 次 $\rm FWT$ 并点乘之后某一项 $x^{s}$ 的值，可以发现

$\begin{aligned} \prod_{i=1}^{n}[x^s]\text{FWT}(2x^{\{a_i\}}+x^{\{\emptyset\}})=\prod_{i=1}^{n}(2\times (-1)^{|s \text{ and } \{a_i\}|}+1)=3^{t}(-1)^{n-t} \end{aligned}$

其中的 $t$ 我们并不知道（只能 $\mathcal{O}(n)$ 求一个），但是最后的值一定是这个形式。

$\rm Magic\ begins!$

我们发现，如果把上式中的 $\prod$ 换成 $\sum$ ，那么有：

$\sum_{i=1}^{n}[x^s]\text{FWT}(2x^{\{a_i\}}+x^{\{\emptyset\}})=\sum_{i=1}^{n}(2\times (-1)^{|s \text{ and } \{a_i\}|}+1)=3t+ (-1)(n-t)=4t-n$

众所周知：

$\rm FWT(A)+FWT(B)=FWT(A+B)$

$\rm IFWT(A)+IFWT(B)=IFWT(A+B)$

于是我们可以先求出 $\text{FWT} (\sum\limits_{i=1}^{n}(2x^{\{a_i\}}+x^{\{\emptyset\}}))$， 然后把每个 $s$ 的 $t$ 解出来，那么真实的 $[x^s]\prod\text{FWT}(\cdots)$ 我们也可以算出来了，对应位置分别算出来后再 $\rm IFWT$ 回去即可。

复杂度 $\mathcal{O}(n\log_2n)$ 。

Code

#include <bits/stdc++.h>
class Input{
private:
    char buf[1000000], *p1, *p2;
public:
    inline char getc(){
        if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
        return p1 == p2 ? EOF : *(p1++);
    }
    template<typename tp>inline Input& operator >> (tp &n){
        n = 0; char c = getc();
        while(!isdigit(c)) c = getc();
        while( isdigit(c)) n = n * 10 + c - 48, c = getc();
        return (*this);
    }
}fin;
const int N = (1 << 20) + 55, mod = 998244353;
using namespace std;
int n;
int a[N], F[N];
long long inv2 = (mod + 1) / 2, inv4 = inv2 * inv2 % mod;
void FWT(int *a, int len, long long tp){
    for(int i = 1; i < len; i <<= 1)
    for(int j = 0; j < len; j += (i << 1))
    for(int k = j; k < i + j; ++k){
        int x = a[k], y = a[k + i];
        a[k] = tp * (x + y) % mod;
        a[i + k] = tp * (x + mod - y) % mod;
    }
}
int qpow(long long b, int t){
    long long ret = 1;
    for(; t; t >>= 1, b = b * b % mod)
        if(t & 1) ret = ret * b % mod;
    return ret;
}
int main(){

    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i], F[a[i]] += 2;
    F[0] += n;
    int m = 1e6, len = 1;
    while(len <= m)
        len <<= 1;
    
    FWT(F, len, 1);

    for(int i = 0; i < len; ++i){
        int t = inv4 * (F[i] + n) % mod;
        F[i] = 1ll * qpow(3, t) * qpow(mod - 1, n - t) % mod;
    }

    FWT(F, len, inv2);

    cout << (F[0] + mod - 1) % mod << endl;
    return 0;
}