异或性质的应用

luxuantao

发布于 2021-02-24 11:20:23

3540

发布于 2021-02-24 11:20:23

文章被收录于专栏：Fdu弟中弟Fdu弟中弟

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

原题链接：EOJ3329

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

Examples

Input

3
3511 3671 4153

Output

Note

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

代码如下：

#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就行了,这就是转移的关键. 那么,异或也有一个奇偶之分，就是^奇数个等于^一个,偶数个等于没^.所以转义方程的写法是那样。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除