2020第一届辽宁省赛 K题 xor
让江姐帮忙指导了一二大概懂了思想
类似一维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