题解：CF2180C XOR-factorization

Imerance1018 · 2026-03-08 19:37:49 · 题解

无脑暴力。

若 k 为奇数输出 k 个 n 即可，下面考虑 k 为偶数的情况。

从高位往低位依次填数。若 n 二进制下该位是 0，只有已填前缀小于 n 前缀的位置可以放 1，记录下来这样的位置，放偶数个。

若该位是 1 则显然放 k-1 个 1，优先放前面已经小了的位置，让前缀相等的数尽可能少。

时间复杂度 O(k \log n)。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(a);i>=(int)(b);i--)
using namespace std;

void solve()
{
    int n,k;
    cin>>n>>k;
    if(k&1)
    {
        rep(i,1,k) cout<<n<<" ";
        cout<<"\n";
        return;
    }
    vector<int> a(k+1,0);
    int tot=0;  //事实上我们可以强制前 tot 个数为已知小于 n 的数
    per(i,30,0)
    {
        if((n>>i)&1)
        {
            if(tot<k) tot++;  //只给第 tot 位不放，小于 n 的数增加
            rep(j,1,k) if(j!=tot) a[j]|=(1<<i);
        }
        else rep(j,1,tot/2*2) a[j]|=(1<<i);
    }
    rep(i,1,k) cout<<a[i]<<" ";
    cout<<"\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}