【题解】2019,6.25模拟赛（异或）

分手后的思念是犯贱 2021-10-26 17:28 333阅读 0赞

## Description ##

给出一个长度为 \\(n\\) 的序列，试把它划分成若干段，是的每段的异或和相同，求一共有多少种方案。答案对 \\(1e9+7\\) 取模。\\(n \\leqslant 500000\\)

## Solution ##

乍一眼看就不会，考虑写个暴力，慢慢优化他。

#### \\(O(N^2)\\) ####

我们很顺利的想到一个状态: \\(f\[i\]\[j\]\\) 表示前 \\(i\\) 个元素，分成的段异或和为 \\(j\\) 的方案数

那么方程就是 \\(f\[i\]\[j\]=\\sum\_\{k=1\}^\{i\}f\[k\]\[\[j\](sum\[i\] \\ xor \\ sum\[k\]==j)\\)。

但是好像这样不能优化，考虑别的状态。

**性质**：我们思考一下发现其实如果序列可以分成若干异或和相同的子序列，那么他们这几个序列的前缀和肯定满足 \\(X 0 X 0 X\\)（其中x是序列的异或和）

因为原本是 \\(XXXXXX\\) 那么做个前缀和，偶数就没了。

我们再考虑一下题目，发现其实序列的断点只能下在 \\(0\\) 和 \\(X\\) 之间。

那么我们想到一种很骚的办法，我们统计一共有几个 \\(0\\) \\(X\\) 。

状态用 \\(f\[i\]\[j\]\\) 表示前 \\(i\\) 个元素，组成的异或前缀和是 \\(j\\) 的方案数。

转移显然：

\\(f\[i\]\[j\]=\\sum\_\{k=1\}^\{i\}(i,k间0的个数) \\times f\[k\]\[j\](sum\[i\]==sum\[k\])\\)

然后发现这个状态的空间复杂度不是很理想 (尽管时间也很不理想)

优化状态

\\(f\[i\]\\) 表示前 \\(i\\) 个元素，组成的异或前缀和是 \\(s\[i\]\\) 时的方案数。

转移：

\\(f\[i\]=\\sum\_\{j=1\}^\{i\} f\[j\] \\times (i到j0的个数)(sum\[j\]==sum\[i\])\\)

这个时候提出 \\(i\\) 到 \\(j\\) 的0的个数,记为cnt\\(\[i\]\[j\]\\),那么方程岂不是：

\\(f\[i\]=cnt\[i\]\[j\] \\times \\sum\_\{j=1\}^\{i\} f\[j\]\\)

#### \\(O(N)\\) ####

那么我们在计一个前缀和数组 \\(g\[i\]=\\sum\_\{j=1\}^\{i\} f\[j\]\\)

更新的时候就可以做到愉快的 \\(O(1)\\) 了。

但是这个状态统计答案是会非常麻烦，所以我们给他变个形：

\\(f\[x\]\\) 表示前缀和为 \\(x\\) 时的方案数

按顺序枚举 \\(i\\) 更新就可以保证正确性

但是如果序列最后的异或前缀和不为 \\(0\\) 的话那么我们只能输出 \\(f\[sum\[n\]\]\\)

为什么呢？ 因为我们必须的得把最后一个 \\(sum\[n\]\\) 和前面的那些序列分开不然会出现分不匀的情况。再加上DP是最优子结构，所以要在最后断开。

如果是 \\(0\\) 的情况，那么我们得首先考虑把所有 \\(0\\) 的位置截开，因为截这些位置是保证可以相等的，那么一共有 \\(2^\{cnt\[1\]\[n\]\}\\) 中方案。

别的我们只需要选择当截成段的异或和为 \\(X\\) 时在任一 \\(0\\) 和 \\(X\\) 相连的地方断开，也就是 \\(g\[x\]\\)

那么到这里终于把这个DP优化成了 \\(O(N)\\)。

欣慰。

// No hacking...#_# #include<bits/stdc++.h> using namespace std; inline char gc(){ static char buf[1<<20],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,1<<20,stdin); if(p1==p2) return EOF; } return *p1++; } #define gc getchar inline int read(){ int x=0;char ch=gc(); while(!isdigit(ch)) ch=gc(); while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x; } int n,ans; const int N=5e5+5,M=(1<<20)+5,P=1e9+7; int a[N],b[N],f[M],sum[N],cnt[N],g[M],pre[M]; inline int power(int a,int b){ int ret=1; while(b){ if(b&1) ret=(1LL*ret*a)%P; a=(1LL*a*a)%P; b>>=1; } return ret; } int main(){ n=read(); for(int i=1;i<=n;++i){ a[i]=read(); sum[i]=(sum[i-1]^a[i]); cnt[i]=cnt[i-1]+(sum[i]==0); } for(int i=1;i<M-5;++i) f[i]=1; ans=1; for(int i=1;i<=n;++i){ if(sum[i]){ f[sum[i]]=(f[sum[i]]+(1LL*g[sum[i]]*(cnt[i]-cnt[pre[sum[i]]]))%P)%P; pre[sum[i]]=i; g[sum[i]]=(g[sum[i]]+f[sum[i]])%P; } else ans=(ans+ans)%P; } if(sum[n]) return printf("%d\n",f[sum[n]]),0; ans=(1LL*ans*power(2,P-2))%P; for(int i=1;i<M-5;++i) ans=(ans+g[i])%P; printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/JCNL666/p/11086159.html