icontofig | 发布于 2019-10-05 22:54:58 | 阅读量 338 | 线性基
发布于 2019-10-05 22:54:58 | 线性基

题目大意

给两个可重集合A,B,求问有多少个数x同时属于A的异或集和B的异或集。

此处的异或集指,从原集合中人与选出若干个数异或出的所有可能结果构成的集合。

题解

如果要我们去枚举每一个数选或者不选,那么一个集合的异或集最多会有250个种元素。这样枚举每种情况的代价太大了,我们如何能够构造一种能够表示异或集内所有可能的值呢?

这里很自然的想到可以对原集合构造异或线性基,线性基的插入就可以判断当前这个数能否被当前构造出的线性基表示。

如果一个数x属于当前集合的异或集,那么x一定能够用线性基向量中的所有位和系数0/1(代表选不选)的组合表示出来。

通过以下韦恩图,我们可以更轻松的理解容斥原理|A∩B| = |A| + |B| - |A∪B|:

其中|A|表示A的秩,也即元素个数。

我们对A、B、A∪B分别构造线性基,并分别求出秩ra,rb,rab,由于同时属于A和B的异或集的元素x一定由A∩B的异或集的线性基向量的各项及0/1系数组合构成,所以最终答案实际上就是2|xor_set(A∩B)|,也即2ra+rb-rab

最终测试的是long long 就能过。

这里的秩当然也可以用高斯消元来解释(高斯消元实际上就对应着方程组矩阵的秩,有大学线性代数基础的同学可能比较清楚),不过高斯消元感觉比线性基更麻烦一些,所以我比赛的时候选择了线性基。

代码

#include <bits/stdc++.h>
int n;
typedef long long ll;
const int maxn = 55;
ll ans,a[maxn],b[maxn];
const int upper = 64;
ll xor_shift[upper];
bool add(ll x){
    bool flag = false;
    for(int i = upper-1;i >= 0;--i){
        if(x & (1ll<<i)){
            if(!xor_shift[i]){
                xor_shift[i] = x;
                flag = true;
                break;
            }
            else{
                x ^= xor_shift[i];
            }
        }
    }
    return flag;
}
ll quick_pow(ll a,ll b){
    ll ret = 1;
    while(b){
        if(b & 1)
            ret *= a;
        a *= a;
        b >>= 1;
    }
    return ret;
}
int main(){
    while(scanf("%d",&n) != EOF){
        ans = 0;
        for(int i = 1;i <= n;++i)
            scanf("%lld",&a[i]);
        for(int j = 1;j <= n;++j)
            scanf("%lld",&b[j]);
        memset(xor_shift,0,sizeof(xor_shift));
        for(int i = 1;i <= n;++i){
            if(add(a[i]))
                ans++;
        }
        memset(xor_shift,0,sizeof(xor_shift));
        for(int i = 1;i <= n;++i){
            if(add(b[i]))
                ans++;
        }
        memset(xor_shift,0,sizeof(xor_shift));
        for(int i = 1;i <= n;++i){
            if(add(a[i]))
                ans--;
        }
        for(int i = 1;i <= n;++i){
            if(add(b[i]))
                ans--;
        }
        printf("%lld\n",quick_pow(2ll,ans));
    }
    return 0;
}



内容更新于: 2019-10-05 22:54:59
链接地址: http://blog.leanote.com/post/icontofig/%E7%89%9B%E5%AE%A2%E6%AC%A2%E4%B9%90%E8%B5%9B4-2017%E6%B9%98%E6%BD%AD%E5%B8%82%E8%B5%9B-C

上一篇: 牛客国庆欢乐赛5 2017四川省赛 D.Dynamic Graph bitset加速 + topsort

下一篇: 牛客国庆欢乐赛5 2017四川省赛 K-2017Revenge bitset加速dp、原根

338 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航