Fork me on GitHub

异或性质的应用

发表于 | 分类于 | 热度 ℃  |  
字数统计 513 字 | 阅读时长 2 分钟

异或的技巧用的好还是很有用的。

原题链接：EOJ3329

给你N个数，输出满足异或和是质数的子集个数（允许有重复元素），答案可能很大，输出模 1e9+7 后的结果。

Examples

Input

1
2
3
3511 3671 4153

Output

1
4

Note

3511，3671，4153，3511 xor 3671 xor 4153 都是质数，所以输出 4。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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就行了,这就是转移的关键. 那么,异或也有一个奇偶之分，就是^奇数个等于^一个,偶数个等于没^.所以转义方程的写法是那样。

donate the author