题意：给一个数组a，从中选择一些元素，构成两个数组s， t，使s数组里的所有元素异或
等于 t数组里的所有元素 位于，求有多少种构成方式。要求s数组里 的所有的元素的下标
小于 t数组里的所有的元素的下标。
分析：比赛的时候，刚开始脑子很乱，后来想了一下思路也敲了，发现自己的程序结果不对
自己一点一点计算后发现自己的程序有一部分计算重复了，其实还是dp的思路不够清晰。
d[i][j]代表第i个数 新产生的结果为数字 j 的个数。
AC代码：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define LL long long
const int maxn = +;
const int mo = +;
using namespace std;
__int64 cnt;
int n, a[maxn];
__int64 d[maxn][maxn], dt[maxn][maxn], temp[maxn][maxn]; int main()
{
int T, i, j, x;
scanf("%d", &T);
while(T--)
{
cnt = ;
memset(d, , sizeof(d));
memset(dt, , sizeof(dt));
memset(temp, , sizeof(temp));
scanf("%d", &n);
for(i = ; i < n; i++)
scanf("%d", &a[i]);
for(i = ; i < n; i++)
{
for(j = ; j < ; j++)
{
if(i!= && temp[i-][j]) //让之前存在的和a[i]异或会产生新的存放在d数组里
{
x = (a[i]^j); //x有可能会大于j，所以不能用d数组直接累加
d[i][x] += temp[i-][j];
}
d[i][j] %= mo; //随时取余很重要，不然会wa
}
d[i][a[i]] ++; //加上自身
for(j = ; j < ; j++)
{
if(i != )
temp[i][j] += temp[i-][j] + d[i][j]; //temp数组用来维护目前所有的
else //结果，并且不可以用d直接加，否则会重复
temp[i][j] = d[i][j];
temp[i][j] %= mo;
}
}
memset(temp, , sizeof(temp));
for(i = n-; i >= ; i--)
{
for(j = ; j < ; j++)
{
if(temp[i+][j])
{
x = (a[i]&j);
dt[i][x] += temp[i+][j];
}
dt[i][j] %= mo;
}
dt[i][a[i]] ++;
for(j = ; j < ; j++)
{
temp[i][j] += temp[i+][j] + dt[i][j];
temp[i][j] %= mo;
}
}
for(i = n-; i >= ; i--)
for(j = ; j < ; j++)
{
dt[i][j] += dt[i+][j]; //这是防止重复的，让dt数组累加，d数组不累加。
dt[i][j] %= mo;
} for(i = ; i < n-; i++)
for(j = ; j < ; j++)
{
cnt += d[i][j]*dt[i+][j]; //用前面的乘以后面的
cnt %= mo;
}
cnt %= mo;
printf("%I64d\n", cnt);
}
return ;
}
顺便贴一下自己在比赛中wa的代码，思路不清。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define LL long long
const int maxn = +;
const int mo = +;
using namespace std;
__int64 cnt, f[maxn];
int n, a[maxn];
__int64 d[maxn][maxn], dt[maxn][maxn]; int main()
{
int T, i, j, tmp;
scanf("%d", &T);
while(T--)
{
cnt = ;
memset(d, , sizeof(d));
memset(dt, , sizeof(dt));
memset(a, , sizeof(a));
memset(f, , sizeof(f));
scanf("%d", &n);
for(i = ; i < n; i++)
scanf("%d", &a[i]);
d[][a[]] = ;
f[a[]] = ;
for(i = ; i < n; i++)
{
for(j = ; j < ; j++)
{
if(f[j])
{
tmp = (a[i]^j);
d[i][tmp] += f[j];
}
d[i][j] %= mo;
}
d[i][a[i]] ++;
f[a[i]] ++;
} memset(f, , sizeof(f));
dt[n-][a[n-]] = ;
f[a[n-]] = ;
for(i = n-; i >= ; i--)
{
for(j = ; j < ; j++)
{
if(f[j])
{
tmp = (a[i]&j);
dt[i][tmp] += f[j];
}
d[i][j] %= mo;
}
dt[i][a[i]] ++;
f[a[i]] ++;
} for(i = n-; i >= ; i--)
for(j = ; j < ; j++)
{
dt[i][j] += dt[i+][j];
dt[i][j] %= mo;
} for(i = ; i < n-; i++)
for(j = ; j < ; j++)
{
cnt += d[i][j]*dt[i+][j];
cnt %= mo;
}
cnt %= mo;
printf("%I64d\n", cnt);
}
return ;
}