题目描述
给你n个数，从中选出两个不相交非空集合S和T，使得S中的每一个元素都在T集合的前面，并且S集合中的所有数的亦或等于T集合中的所有数的与，求方案数 mod 10^9+7。
输入
The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains a integers n.
The next line contains n integers a_1,a_2,...,a_n which are separated by a single space.
n<=10^3, 0 <= a_i <1024, T<=20.
输出
For each test case, output the result in one line.
样例输入
2
3
1 2 3
4
1 2 3 3
样例输出
1
4
题解
dp
设$s[i][j]$表示前$i$个数选$i$，选出的数的亦或为$j$的方案数，那么直接使用前缀和优化，转移时枚举之前的$j$，与当前位置计算得出新的$j$即可。
设$t[i][j]$表示从$i$到$n$选$i$，选出的数的与为$j$的方案数，那么转移同理。
最后枚举$S$/$T$集合的第一个数，使用乘法原理计算即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define m 1024
#define mod 1000000007
using namespace std;
int a[m] , fs[m][m] , ss[m][m] , ft[m][m] , st[m][m];
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
int n , i , j , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);
memset(fs , 0 , sizeof(fs)) , memset(ss , 0 , sizeof(ss));
memset(ft , 0 , sizeof(ft)) , memset(st , 0 , sizeof(st));
ss[0][0] = st[n + 1][m - 1] = 1;
for(i = 1 ; i <= n ; i ++ )
{
for(j = 0 ; j < m ; j ++ ) fs[i][j ^ a[i]] = (fs[i][j ^ a[i]] + ss[i - 1][j]) % mod;
for(j = 0 ; j < m ; j ++ ) ss[i][j] = (ss[i - 1][j] + fs[i][j]) % mod;
}
for(i = n ; i ; i -- )
{
for(j = 0 ; j < m ; j ++ ) ft[i][j & a[i]] = (ft[i][j & a[i]] + st[i + 1][j]) % mod;
for(j = 0 ; j < m ; j ++ ) st[i][j] = (st[i + 1][j] + ft[i][j]) % mod;
}
for(i = 1 ; i < n ; i ++ )
{
ss[i][0] -- ;
for(j = 0 ; j < m ; j ++ ) ans = (ans + (long long)ss[i][j] * ft[i + 1][j]) % mod;
}
printf("%d
" , ans);
}
return 0;
}