P9033 「KDOI-04」XOR Sum 题解

· · 题解

凯文一眼秒了这题，本蒟蒻却做了半个小时。

我们用 m2 表示 m 二进制下的位数，用 k2 表示 k 二进制下的位数.

无解的情况很好判断，当 m2 小于 k2 时无解。

我们使 a_1=2^{k2}，求 a_2，使 a_2\oplus a_1=k，即 a_2=a_1\oplus k。

在二进制下，a_1 的位数和 k 的位数相同，所以 a_2 一定小于 a_1。

至于后面的数，我们可以让他们都等于 0。

记得特判 n=0 的情况。

代码

#include<bits/stdc++.h>
#include<cstdio>
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
using namespace std;
int f(int a,int n){//快速幂
    int ans=1;
    while(n){
        if(n&1)ans=ans*a;
        a*=a;
        n/=2;
    }
    return ans;
}
int T,n,m,k,m2,k2;
int main(){
    T=read();
    while(T--){
        n=read();k=read();m=read();
        m2=log2(m);
        k2=log2(k);
        if(m2<k2){printf("-1\n");continue;}
        if(n==1){
            if(k>m)printf("-1\n");
            else printf("%d \n",k);
            continue;
        }
        int a1=f(2,k2),a2=0;
        printf("%d ",a1);
        a2=a1^k;
        printf("%d ",a2);
        for(int i=3;i<=n;i++)printf("0 ");
        printf("\n");
    }
    return 0;
}