题目大意：给定一个序列，要求选出两个集合，S和T，要求S中选中的元素的下标都要小于T中元素的下标。
而且说S中元素的亦或和要等于T中元素取且的和。
解题思路:dp， 思路非常好想。就是细节比較恶心。
#include#include #include using namespace std;typedef __int64 ll;const int maxn = 1024;const ll MOD = 1e9+7;int n, num[maxn];ll l[maxn][maxn+10][2], r[maxn][maxn+10];void init () { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &num[i]);}ll solve () { memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r)); for (int i = 1; i < n; i++) { l[i][num[i]][1]++; for (int j = 0; j < maxn; j++) { l[i+1][j][1] = (l[i][j^num[i+1]][1] + l[i][j^num[i+1]][0]) % MOD; l[i+1][j][0] = (l[i][j][1] + l[i][j][0]) % MOD; } } for (int i = n; i; i--) { r[i][num[i]]++; for (int j = 0; j < maxn; j++) { r[i-1][j] = (r[i-1][j] + r[i][j]) % MOD; r[i-1][j&num[i-1]] = (r[i-1][j&num[i-1]] + r[i][j]) % MOD; } } ll ans = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < maxn; j++) { /* if (l[i][j] * r[i+1][j]) printf("%d %d %lld %lld\n", i, j, l[i][j], r[i+1][j]); */ ans = (ans + l[i][j][1] * r[i+1][j] % MOD) % MOD; } } return ans;}int main () { int cas; scanf("%d", &cas); while (cas--) { init(); printf("%I64d\n", solve()); } return 0;}