我要评论让江姐帮忙指导了一二大概懂了思想
类似一维dp的动态规划
定义： f [ i ] f[i] f[i]为前i个值的拆分方法数, x o r [ i ] xor[i] xor[i]代表前i个值的异或和
f
[
i
]
=
∑
j
=
1
i
f
[
j
]
(
x
o
r
[
j
]
⊕
x
o
r
[
i
]
=
x
)
f[i]=\sum_{j=1}^if[j] \left(xor[j]\oplus xor[i]=x \right)
f[i]=∑j=1if[j](xor[j]⊕xor[i]=x)
而要找到这些符合公式的
j
j
j,只需利用
a
⊕
b
=
c
⇒
a
=
b
⊕
c
a\oplus b=c \Rightarrow a=b\oplus c
a⊕b=c⇒a=b⊕c
即
f
[
i
]
=
∑
j
=
1
n
f
[
j
]
(
x
o
r
[
j
]
=
x
o
r
[
i
]
⊕
x
)
⇔
s
u
m
(
x
o
r
[
i
]
⊕
x
)
f[i]=\sum_{j=1}^nf[j] \left(xor[j]=xor[i]\oplus x \right) \Leftrightarrow sum(xor[i]\oplus x)
f[i]=∑j=1nf[j](xor[j]=xor[i]⊕x)⇔sum(xor[i]⊕x)
因此 只需利用map记录当前各异或和的值对应的方案数即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
map<int, int> m;
const int mod = 1e9 + 7;
int _mod(int x) {return x -= x >= mod ? mod : 0; }
int main()
{
int n, x,t;
int now = 0;
int result=0;
m[0] = 1;
scanf("%d%d", &n, &x);
while (n--)
{
scanf("%d", &t);
now ^= t;
result = m[now ^ x];
m[now] = _mod(m[now] + result);
}
printf("%d", result);
}
本文地址：https://blog.csdn.net/qq_45961715/article/details/109269611
您可能感兴趣的文章:
- vue init初始化项目后 npm run dev报错 10% building modules 1/1 modules 0 activeevents
- axios 处理 302 状态码的解决方法
- [Intervention] Unable to preventDefault inside passive event listener due to target being treated as passive. See https://www.chromestatus.com/feature
- react-native 在新版Xcode（10+）中运行出现的问题： node_modules/react-native/third-party/glog-0.3.4 , C compiler cannot create executables
- 使用puppeteer爬取网站并抓出404无效链接
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论