P12025 [USACO25OPEN] Sequence Construction S
题目描述
最近，农夫约翰农场里的奶牛们迷上了观看《炼乳神探》这档节目。节目讲述了一头聪明的奶牛侦探CowCow解决各类案件的故事。贝茜从节目中发现了新的谜题，但答案要等到下周的下一集才会揭晓！请帮她解决这个问题。
给定整数 \(M\) 和 \(K\) \((1 \leq M \leq 10^9, 1 \leq K \leq 31)\)。请选择一个正整数 \(N\) 并构造一个包含 \(N\) 个非负整数的序列 \(a\)，满足以下条件：
- \(1 \le N \le 100\)。
- \(a_1 + a_2 + \dots + a_N = M\)。
- \(\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K\)。
如果不存在这样的序列，输出 \(-1\)。
\(\dagger \text{ popcount}(x)\) 表示整数 \(x\) 的二进制表示中 \(1\) 的位数。例如，\(11\) 的 popcount 是 \(3\)，\(16\) 的 popcount 是 \(1\)。
\(\dagger \oplus\) 表示按位异或运算符。
输入包含 \(T\) (\(1 \le T \le 5 \cdot 10^3\)) 组独立测试用例。
输入格式
第一行包含 \(T\)。
每个测试用例的第一行也是唯一一行包含 \(M\) 和 \(K\)。
保证所有测试用例都是唯一的。
输出格式
按以下方式输出 \(T\) 个测试用例的解答：
如果无解，该测试用例对应的唯一一行输出应为 \(-1\)。
否则，该测试用例的第一行输出应为序列长度 \(N\)（\(1 \le N \le 100\)），第二行输出应包含 \(N\) 个用空格分隔且满足条件的整数（\(0 \le a_i \le M\)）。
输入输出样例 #1
输入 #1
3
2 1
33 5
10 5
输出 #1
2
2 0
3
3 23 7
-1
说明/提示
在第一个测试用例中，数组 \(a = [2, 0]\) 的元素之和为 \(2\)。其 popcount 的异或和为 \(1 \oplus 0 = 1\)，因此所有条件均被满足。
在第二个测试用例中，数组 \(a = [3, 23, 7]\) 的元素之和为 \(33\)。其 popcount 的异或和为 \(2 \oplus 4 \oplus 3 = 5\)，因此所有条件均被满足。
其他有效数组包括 \(a = [4, 2, 15, 5, 7]\) 和 \(a = [1, 4, 0, 27, 1]\)。
可以证明第三个测试用例不存在有效数组。
- 测试点 \(2\)：\(M \leq 8, K \leq 8\)。
- 测试点 \(3\sim 5\)：\(M > 2^K\)。
- 测试点 \(6\sim18\)：无额外限制。
解题报告
比较巧妙的构造题。
由于第三个条件限制非常强，我们得先考虑这一条。
先不管其他，我们考虑满足第三条需要那些 \(\text{popcount}(x)\)。
看到异或，我们考虑按二进制位分析（经典方法），比如 \(k=5_{10}=101_2=100_2+1_2=4_{10}+1_{10}\)，在要求数组长度最小的情况下，t贪心的用 \(\text{popcount}(1111_2)=4\) 和 \(\text{popcount}(1_2)=1\) 来满足是最优的，其他情况同理。也就是说，对于 \(k\)，如果它的二进制的第 \(x\) 位为 \(1\)，我们就把 \(2^x-1\) 加进我们的序列中，如果这样的数的总和 \(sum\) 已经大于 \(m\)，显然是无解的，否则，令 \(m \leftarrow m-sum\)。
考虑怎么处理 \(m>0\) 的情况，由于我们已经满足了第三条件，就只需要将其他数的 \(\text{popcount}\) 的异或起来的结果为 \(0\)，最简单的情况：使所有数的 \(\text{popcount}\) 都相等，在进一步，最好直接使每一个数都相等！由于要求数组长度尽可能小以满足条件一，我们期望可以把 \(m\) 分成两个相同的数。
但显然事情没这样美好，只有 \(m\) 为偶数时可以这么搞，为奇数时怎么办？
有一个挺重要的性质：\(\text{popcount}(2)==\text{popcount}(1)\)，用于最后微调。
我们分讨 \(m\) 为奇数时的情况：
- 对于 \(m=1\)，由于以上性质，我们可以将序列中原有的数字 \(1\) 改成 \(2\) 就可以了，若没有 \(1\) 就无解。
- 对于 \(m>1\)，由于 \(1 \oplus 2=0\) 且有以上性质，我们可以先拆出一个 \(1\) 和 \(2\) 转化为偶数，再处理就好了。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=101100;
const int lg=32;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n,m,K;
int ans[N];#define NO { puts("-1");continue; }inline bool divide()
{while(K){int tmp=K&(-K);ans[++n]=(1<<tmp)-1;K-=tmp,m-=(1<<tmp)-1;if(m<0) return false;}return true;
}inline void out()
{printf("%d\n",n);for(int i=1;i<=n;i++)printf("%d ",ans[i]);putchar('\n');
}signed main()
{int nQ=read();while(nQ--){m=read(),K=read();memset(ans,0,sizeof(ans)); n=0;if(!divide()) NO;if(m==1){bool flag=false;for(int i=1;i<=n;i++)if(ans[i]==1){ans[i]=2,flag=true;break;}if(!flag) NO;n++;out();continue;}if(m>0 && m&1){ans[++n]=1,ans[++n]=2;ans[n+1]=ans[n+2]=(m-3)/2;n+=2;}if(m>0 && !(m&1) ){ans[n+1]=ans[n+2]=m/2;n+=2;}out();}return 0;
}