首先考虑暴力的转移，当枚举到第 $i$ 个数时，我们尝试将之前所有的有效状态的 $P,Q,R$ 均与 $a_i$ 尝试去异或，然后检测合法性。于是就有：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| la[{0,0,0}] = 1;
for (int i = 1;i <= n;++i)
{
for (auto item : la)
{
node v = item.first;
int x = v.p,y = v.q,z = v.r;
if (y == z || (x ^ a[i]) == y || (x ^ a[i]) == z) dp[{x ^ a[i],y,z}] += la[v];
if (x == z || (y ^ a[i]) == x || (y ^ a[i]) == z) dp[{x,y ^ a[i],z}] += la[v];
if (x == y || (z ^ a[i]) == x || (z ^ a[i]) == y) dp[{x,y,z ^ a[i]}] += la[v];
}
for (auto item : dp) dp[item.first] %= MOD;
la.clear ();la = dp;dp.clear ();
}
|
但这样显然会有很多冗余的转移以及判断，考虑异或的性质去优化。
回顾一下题面，对于一个数字只能选择 $P,Q,R$ 中的一个去异或，那么处理完 $a_i$ 后，$P \oplus Q \oplus R = \oplus _{j = 1}^i a_j = p_i$。由于 $P,Q,R$ 不能两两互异，此时设 $(P,Q,R)$ 中相同的数为 $x$，由于 $x \oplus y \oplus y = x$，故可能的有效状态为 $(x,x,p_i),(x,p_i,x),(p_i,x,x)$ 中的一个。
设 $dp_{i,x}$ 表示在处理第 $i$ 个数后相同的数为 $x$ 的方案数。则 $(x,x,p_i)$ 的上一个状态可能为 $(x \oplus a_i,x,p_i)$ 或 $(x,x,p_i \oplus a_i)$。
上一个状态为 $(x \oplus a_i,x,p_i)$
由于要保证状态的合法性，需要分类讨论具体是哪两个数相同：
- $x \oplus a_i = x \Rightarrow a_i = 0$，与题干矛盾，故不可能成立。
- $x \oplus a_i = p_i \Rightarrow x = p_{i - 1}$，此时转移方程为 $dp_{i,x} = dp_{i,p_{i - 1}} = dp_{i-1,p_i}$。
- $x = p_i$，此时转移方程为 $dp_{i,x} = dp_{i,p_i} = dp_{i - 1,p_i}$
上一个状态为 $(x,x,p_i \oplus a_i)$
显然，转移方程为 $dp_{i,x} = dp_{i - 1,x}$。
通过观察可以发现，$dp_{i,x} \leftarrow dp_{i - 1,x}$ 不成立当且仅当 $x = p_{i - 1}$ 的情况，其余直接继承。最终状态为 $(x,x,p_i)$，代入 $x$ 后是 $(p_{i - 1},p_{i - 1},p_i)$。由 $(p_{i - 1},p_{i - 1},p_{i - 1})$ 转移共有三种方式，而由 $(p_{i - 1},p_i,p_i)$ 转移共有两种方式。同时，可以发现可以利用滚动数组优化，因此可以有：
当然，初始条件为 $dp_{0} = 1$。数字过大，离散化或者直接用 map 即可。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,a[MAX],p[MAX];ll ans;
map <int,ll> dp;
int main ()
{
t = read ();
while (t--)
{
n = read ();ans = 0;dp.clear ();
for (int i = 1;i <= n;++i) a[i] = read (),p[i] = p[i - 1] ^ a[i];
dp[0] = 1;
for (int i = 1;i <= n;++i) dp[p[i - 1]] = (dp[p[i]] * 2 + dp[p[i - 1]] * 3) % MOD;
for (auto item : dp) ans = (ans + item.second) % MOD;
printf ("%lld\n",ans);
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
