首页 > 代码库 > hdu3949

hdu3949

2024-09-20 22:20:27   203人阅读

线性基？

线性基在我的理解下是一种向量基底，就是说每个数a[i],都能通过线性基组合出来。又因为线性基只有01，所以系数只有01

这道题感觉就是确定每一个二进制位能不能通过xor组合出来，然后因为二进制可以通过贪心确定大小，因为选择最高位肯定是最大的，所以我们可以拆分k来确定每一位选还是不选。

消元之后就能确定每个二进制位是否能选出来，因为高斯消元完了消出一组解，就肯定能通过选或不选某个数组合出来，肯定不会矛盾，比如说两个位是1，他们的组合矛盾了，这是不可能的，因为高斯消元求出了一组方程的解，解肯定满足任意一条方程。

now的意思是能够通过now个元素组合出所有的数，这样的意思也就是有2^now-1个元素，其他的数都是重复。

又理解了一下，就是把每个数消成只有一个1或0个1，0个1选不选无所谓，1个1有选或不选。所以就是选或不选变成了两个数，也就是我们有多少个消完后的a[i]不是0，那么我们就有2^个数-1个不重复的数（0不能出现） 这个东西和向量挺像的。

还有一点不明白...

技术分享 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010;
int n, m, now;
ll a[N], bin[70];
void gauss()
{
    now = 1;
    for(int i = 61; i >= 0; --i)
    {
        int j = now;
        while(j <= n && !(a[j] & bin[i])) ++j;
        if(j > n) continue; //这位没有，不能弄出来0 
        swap(a[now], a[j]);
        for(int j = 1; j <= n; ++j) if(j != now && a[j] & bin[i]) a[j] ^= a[now];
        ++now; //下一位 
    }
    --now; //可以弄出来2^now-1个数 
}
ll query(ll k)
{
    ll ret = 0;
    if(now != n) --k;
    if(k >= bin[now]) return -1;
    for(int i = 1; i <= now; ++i) if(k & bin[now - i]) ret ^= a[i];
    return ret;
}
int main()
{
    bin[0] = 1; for(int i = 1; i <= 61 ; ++i) bin[i] = bin[i - 1] << 1;
    int T, cas = 0; scanf("%d", &T);
    while(T--)
    {
        printf("Case #%d:\n", ++cas); 
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        gauss();
        scanf("%d", &m);
        while(m--)
        {
            ll k; scanf("%lld", &k);
            printf("%lld\n", query(k));
        }
    }
    return 0;
}
View Code

 

hdu3949


联系
我们