子序列

题目描述

垫底哥学了两年 OI 最近刚刚学会了 xor 和子序列。

他得到了一个长度为 \(n\) 的数组 \(a_1, a_2, a_3,\dots, a_n\)，他想知道 xor 值为 \(0\) 的子序列最长是多少。

然而垫底哥除了垫底其它什么都不会，他就找你解决这个问题。

输入格式

第一行一个正整数 \(n\)。

第二行 \(n\) 个整数，分别表示 \(a_1, a_2, a_3, \dots, a_n\)。

输出格式

一行 \(1\) 个整数，表示答案。

数据规模与约定

对于所有数据，满足 \(1 ≤ n ≤ 5 × 10^5, 0 ≤ a_i ≤ 5 × 10^5\)。

记 \(A = \max\{a_1, a_2, \cdots , a_n\}\)：

• \(Subtask \ 1\)（\(10\%\)）：\(n ≤ 20\)；

• \(Subtask\ 2\)（\(20\%\)）：\(n ≤ 100\)，\(A ≤ 100\)；

• \(Subtask 3\)（\(30\%\)）：\(n ≤ 3000，A ≤ 3000\)；

• \(Subtask 4\)（\(40\%\)）：无特殊限制。

考虑补集转换，设\(S=a_1\ xor \ a_2 \ xor \dots \ xor \ a_n\)，求最少的可以异或出\(S\)的数的个数。

由线性姬的构造可以得到个数一定不大于\(\log A\)

然后可以DP一下，\(dp_{i,j}\)代表\(i\)个数是否可以异或出\(j\)

可以拿FWT优化这个转移，直接裸优化是\(n\log^2A\)的，不过我们发现只需要单点询问一个数是否有值就可以了，于是可以先正变换，然后每次单点做一次\(O(n)\)的逆变换

Code:

#include 
    
     #define beelovely 2333const int mod=998244353;#define add(a,b) (a+b>=mod?a+b-mod:a+b)#define mul(a,b) (1ll*(a)*(b)%mod)const int N=(1<<19)+10;int n,s,mx,a[N],popcnt[N],f[N],b[N],lim=1;void FWT(int *a){    for(int le=1;le
     
      <<=1)        for(int p=0;p
      
       <<1)            for(int i=p;i
       
        x?mx:x;    while(lim<=mx) lim<<=1;    for(int i=1;i
        
         >1]+(i&1);        b[i]=popcnt[i]&1?mod-1:1;    }    f[0]=b[0]=1;    FWT(a),FWT(f);    while(beelovely)    {        int dew=0;        for(int i=0;i