子序列

题目描述

垫底哥学了两年 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 <cstdio> #define beelovely 2333 const 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<lim;le<<=1)for(int p=0;p<lim;p+=le<<1)for(int i=p;i<p+le;i++){int x=a[i],y=a[i+le];a[i]=add(x,y);a[i+le]=add(x,mod-y);} } int main() {scanf("%d",&n);for(int x,i=1;i<=n;i++) scanf("%d",&x),s^=x,++a[x],mx=mx>x?mx:x;while(lim<=mx) lim<<=1;for(int i=1;i<lim;i++){popcnt[i]=popcnt[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<lim;i++) dew=add(dew,mul(f[i],b[s&i]));if(dew) break;--n;for(int i=0;i<lim;i++) f[i]=mul(f[i],a[i]);}printf("%d\n",n);return 0; }

---

2019.1.17

转载于:https://www.cnblogs.com/butterflydew/p/10284431.html

总结

以上是生活随笔为你收集整理的子序列 解题报告的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。