异或的技巧用的好还是很有用的。
原题链接：EOJ3329
给你N个数，输出满足异或和是质数的子集个数（允许有重复元素），答案可能很大，输出模 1e9 7 后的结果。
Examples
Input
代码语言：javascript复制3
3511 3671 4153Output
代码语言：javascript复制4Note
3511，3671，4153，3511 xor 3671 xor 4153 都是质数，所以输出 4。
代码如下：
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long LL;
const int MAXN = 1e4 17;
const int MOD = 1e9 7;
bool prime[9025];
void sieve( )
{
memset(prime, true, sizeof(prime));
prime[0]=prime[1]=false;
for(int i=2;i*i<=9000; i)
for(int k=2;k*i<=9000; k)
prime[k*i]=false;
}
int a[MAXN];
LL dp[2][8192 17];
int main(int argc, char *argv[])
{
sieve();
int n,x = 0 ;
cin>>n;
map<int,int> mp;
for (int i = 0; i < n; i)
{
int temp;
scanf("%d",&temp);
if(!mp[temp])
a[x ] = temp;
mp[temp] ;
}
int now = 0,last = 1;
dp[now][0] = 1;
for (int i = 0; i < x; i)
{
int odd = (mp[a[i]] 1)/2;
int even = mp[a[i]] 1-(mp[a[i]] 1)/2;
swap(now,last);
for (int j = 0; j < 8192; j)
dp[now][j] = ((dp[last][j^a[i]]*odd)%MOD dp[last][j]*even)%MOD;
}
LL ans = 0;
for (int i = 2; i <= 8192; i)
if(prime[i])
ans = (ans dp[now][i])%MOD;
cout<<ans<<endl;
return 0;
}先用素数筛求出2到9000之间的所有素数。map记录每个数出现次数。dp【i】【j】表示从前i个不同的数中组成的所有集合中，能使得异或和的结果为j的集合个数（注意这里第i个数可以一个都不取）。为减小空间还用到了滚动数组。
dp[now][j] = ((dp[last][j^a[i]]*odd)%MOD dp[last][j]*even)%MOD;
这句话的理解是关键，dp[now][j]有两种来源,可以通过以下知识点来理解。
知识点补充： a^b^b = a ， 也就是说,异或是可以抵消的,放到这里来说,假如我想知道x^a = b中的x,那么我只需要把b再^一下a就行了,这就是转移的关键. 那么,异或也有一个奇偶之分，就是^奇数个等于^一个,偶数个等于没^.所以转义方程的写法是那样。
