1 条题解

  • 0
    @ 2024-4-1 17:28:57
    #include <bits/stdc++.h>
     //#define int long long
    #define help {cin.tie(NULL); cout.tie(NULL);}
    #define pb push_back
    #define fi first
    #define se second
    #define mkp make_pair
    using namespace std;
     
    typedef long long LL;
    typedef pair<int, int> PII;
    typedef pair<LL, LL> PLL;
     
    template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
    template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
     
    template <typename T> void inline read(T &x) {
        int f = 1; x = 0; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
        while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
        x *= f;
    }
    
    const int N=10005;
    int t,n,k,q;
    LL x,a[N];
    int main()
    {
        scanf("%d",&t);
        for(int T=1;T<=t;T++)
        {
        	printf("Case #%d:\n",T);
        	scanf("%d",&n);
        	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        	k=0;
        	for(int i=62;i>=0;i--)
        	{
        		for(int j=k;j<n;j++)
        			if(a[j]>>i&1)
        			{
        				swap(a[k],a[j]);
        				break;
        			}
        		if(!(a[k]>>i&1))continue;
        		for(int j=0;j<n;j++)
        			if(j!=k&&(a[j]>>i&1))a[j]^=a[k];
        		k++;
        		if(k==n)break;
        	}
        	reverse(a,a+k);
        	bool f=k<n;
        	scanf("%d",&q);
        	while(q--)
        	{
        		scanf("%lld",&x);
        		x-=f;
        		if(x>=(1ll<<k))
        		{
        			puts("-1");
        			continue;
        		}
        		LL res=0;
    			for(int i=0;i<k;i++)
    				if(x>>i&1)res^=a[i];
        		printf("%lld\n",res);
        	}
        }
        return 0;
    }
    
    • @ 2024-4-1 17:30:17

      由于线性基表示的空间和原向量组表示的空间等价,所以可以先求出线性基,用线性基来表示第k小数,由于线性基中每一个最高位的元素仅有一个,可以将每一个线性基元素当作一位,求第k小数即将k的二进制数表示出来相应乘以线性基元素,另外由于线性基不能表示0,所以需要判断原向量组是否线性相关或无关,如果向量组的秩k < n,则线性相关,即可以表示出0,否则不能

    • @ 2024-4-1 17:30:59

      时间复杂度:O(63n)

  • 1

信息

ID
121
时间
1000ms
内存
128MiB
难度
9
标签
递交数
7
已通过
6
上传者