先发现以下两个性质:
- 对于所有段,它们的异或和就是所有数的异或和。
- 由于每段的异或和都一样,设为 \(d\),并设 \(s\) 为所有数的异或和,总共分成了 \(x\) 段,则有 \(s=[x\bmod2=1]d\)。
设 \(\left\{A\right\}\) 的前缀异或和为 \(\left\{pre\right\}\)。
分类讨论。
如果 \(s\ne0\),这个比较清晰,说明 \(d=s\) 且 \(x\) 是奇数,考虑所有 \(x\) 段的最后一个数的位置 \(p_1,\cdots,p_x\),那么说明 \(pre_{p_i}=[i\bmod2=1]d\),因此问题变成在 \(1,\cdots,n\) 选奇数个位置,且 \(n\) 必须选,满足奇数位置上的 \(pre=d\),偶数位置上的 \(pre=0\)。
考虑 DP,设 \(f(i,0/1)\) 表示前 \(i\) 个数,选了偶数/奇数个位置的方案数。则有
\[f(i,0)=\left\{\begin{matrix} f(i-1,0)& a_i\ne0 \\f(i-1,0)+f(i-1,1)& a_i=0 \end{matrix}\right.\]
\[f(i,1)=\left\{\begin{matrix} f(i-1,1)& a_i\ne d \\ f(i-1,1)+f(i-1,0)& a_i=d \end{matrix}\right.\]
否则若 \(s=0\),继续分类讨论,若分成的段数是 \(x\) 是奇数,则说明 \(d=0\),问题同上,否则 \(d\) 未知,问题变成在 \(1,\cdots,n\) 中选偶数个位置,且 \(n\) 必须选,满足奇数位置上的 \(pre=d\),偶数位置上的 \(pre=0\)。
如果对每个 \(d\) 都 \(\mathcal O(n)\) 跑一遍 DP,将会爆炸,但是注意到转移只会在 \(pre=0\) 或 \(pre=d\) 的位置更新 \(f\),于是预处理出所有 \(pre_i=d\) 的位置,然后对 \(pre_i=0\) 的位置进行前缀和预处理,就可以快速转移了。
时间复杂度 \(\mathcal O(n)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005, M = 1 << 20, mod = 1e9 + 7;
int n;
int pre[N], sum[N];
vector <int> pos[M];
bool vis[M];
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int calc(int d) {
if (!d) {
int res = 1;
for (int i = 0; i + 1 < pos[0].size(); ++i) res = res * 2 % mod;
return res;
}
int odd = 0, even = 1, lst = 0;
for (int i = 0; i + (pre[n] == d) < pos[d].size(); ++i) {
add(even, 1ll * odd * (sum[pos[d][i]] - sum[lst]) % mod), add(odd, even);
lst = pos[d][i];
}
add(even, 1ll * odd * (sum[n - 1] - sum[lst]) % mod);
if (pre[n] == d) return even;
else return odd;
}
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; ++i) scanf("%d", &x), pos[pre[i] = pre[i - 1] ^ x].push_back(i), sum[i] = sum[i - 1] + (pre[i] == 0);
if (pre[n]) return printf("%d", calc(pre[n])), 0;
else {
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (vis[pre[i]]) continue;
vis[pre[i]] = 1, add(ans, calc(pre[i]));
}
printf("%d", ans);
}
return 0;
}
```AT_diverta2019_e
原文地址:http://www.cnblogs.com/Kobe303/p/16904770.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性