题目要求
给定一个正整数数组a，同时给定三个变量P,Q,R，初始值为0。每个a[i]都需要和三个变量中的一个数进行异或计算，并且每次操作后都必须保证三个变量不两两不同，也就是说至少有两个数相同，问你有多少种方法能够满足题目条件，答案需要对1e9+7求余。
数据范围
1≤n≤2* 1 0 5 10^{5} 105 , 1≤ a i a_{i} ai≤ 1 0 5 10^{5} 105
这道题是CF上2300的题目，真的很难，如果不是队友让我看这道题我估计直接不看这道题了。
很多个地方都是很难想明白的。并且我自己也比较笨吧，网上的题解也都是跳步了的，但是我跟不上这个思维，所以很多地方是想了好久才一点一点梳理清楚的。
分析
首先第一点就是这道题要想到在这道题可以用DP做的，用DP做的理由是我每次都要放一个数字进来进行异或的这个过程，状态有限并且，异或的一个经常用的到的性质就是可逆性，就是说x ^ y ^ z , 我如果要想知道x ^ y 的结果，我只需要让整个式子再对z进行一次异或计算就可以了，也就是说我可以知道上一个状态，那既然我能知道上一个状态是什么，我只要知道上一个状态有哪些，那么我能够达到当前状态的方法个数不就是所有上一个状态的方法个数之和吗？
所以这道题可以用DP来做
那么我们就要想着如何表示出这个DP状态，我们总不能说一个dp[x][y][z]来表示三个数是x,y,z吧，既然我们这里找不到能够表示的DP状态，我们应该去找一些性质能够帮助我们去表示状态的而不是看到现在不能表示DP状态就放弃DP
首先每一个数字都要对这三个中的一个进行异或计算，所以P ^ Q ^ R=pre[i],其中pre[i]表示前i个数字的异或和。 然后就是题目要求的至少有两个数字是相等的，这两个条件结合，我们不难得到结论就是：到达第i个数字的状态肯定是x,x,pre[i]的形式 ，因为至少两个数字相等异或的时候就已经抵消了，肯定要剩下一个数字是pre[i]。既然如此我们就可以设状态为dp[i][x],表示到第i个数时x为x的情况有多少种方法 。
状态表示出来了，首先我们不要着急想着递推关系，而是要先梳理清楚一点：既然我的状态这样子表示了，那么我应该输出的是什么 ，我们要的是全部数字都进行异或计算后满足至少两个数字相等的方法总个数，所以我们的最终答案应该是dp[n][x]的总和。
现在弄清楚输出结果了，我们再来看递推关系，正如前面所说，我们要想知道当前状态的方法个数，只要知道全部可能的上一个状态的方法总数之和就好了。对于当前状态(x,x,pre[i]),也就是两种情况：(x,x,pre[i-1])和
(x^a[i],x,pre[i])。
对于第一种情况,那就是dp[i-1][x].
对于第二种情况,由于每次操作后都要满足至少两个数字相等，也就是至少这三种情况满足一个：x ^ a[i] = x , x ^ a[i] = pre[i]（也就是x = pre[i-1]) , x = pre[i] 。 其中由于a[i] ≠ 0 ，所以只可能是后两种情况。
当x=pre[i]的时候,那么当前状态就是(pre[i],pre[i],pre[i]),可以发现这种状态就只能来自(pre[i-1],pre[i],pre[i]),也就是说dp[i][pre[i] = dp[i-1][pre[i]].
当x=pre[i-1]的时候,当前状态为(pre[i-1],pre[i-1],pre[i]),这种状态可以来自(pre[i-1],pre[i-1],pre[i-1])以及(pre[i],pre[i],pre[i-1]),前一种a[i]和三个位置的pre[i-1]进行异或计算能够得到当前状态,而后一种和两个位置的pre[i]进行异或计算可以得到当前状态，所以说:
dp[i][pre[i-1] = 3 * dp[i-1][pre[i-1]] + 2 * dp[i-1][pre[i]]
我在推的时候在这个地方卡住很久，队友也提出一点：就是我可以全部数字只对一个变量进行异或，或者在满足条件之后只对一个变量进行异或。这个时候我们就要整理我们上面得到的递推关系了。我们可以发现我们其实状态关注的点在于x的值是多少，并且对于只对一个变量进行异或的情况，其实不就是x的值没变的情况吗， 这种情况的方法数量可以发现是不会变的。 所以我们为了方便要变更一下DP数组的构造方式，应该变为dp[x]表示当x为某个值的时候的方法个数。
递推关系式就为：dp[pre[i-1]] = 3 * dp[pre[i-1]] + 2 * dp[pre[i]]
还要注意一点就是我们最后要将所有的dp[x]累加起来，并且x的值是可以很大的，所以我们可以用map来存储dp值，最后遍历map累加就好
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=1000100;
void init() {
}
int a[N];
int pre[N];
void solve() {
init();
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],pre[i] =pre[i-1] ^ a[i];
int ans=0;
map<int,int>dp;
dp[0]=1;
for(int i=1;i<=n;i++) {
dp[pre[i-1]] = ( (3 * dp[pre[i-1]]) % MOD + (2 * dp[pre[i]]) % MOD ) %MOD;
}
for(auto [x,y] : dp ) {
ans += y;
ans %= MOD;
}
cout<<ans<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
总结：
第一点是要能够根据集合状态递推这三点分析出这道题用的是dp
第二点是在分析出dp的状态之后，发现有地方不合理应该是想着找题目条件以及相关性质让其能够用在dp上而不是放弃dp
第三点是在表示出状态之后应该想一下这种状态应该如何得到最终结果，再去找递推关系
第四点是发现有地方别扭的时候要看看dp状态是否方便计算，是否有多余的维度或者少了某个维度
第五点就是要结合dp状态去推，不要舍本逐末，要表示当前的这种状态表示为什么，可以由哪些状态递推过来
京公网安备 11010502036488号