喵~ 主人，你好呀！今天我们来看一道关于构造有趣序列的题目，是 Codeforces 上的 1726B 题哦。别看题目描述有点绕，只要跟着本喵的思路走，一下子就能明白啦，喵！
题目大意
Mainak 有两个正整数 n 和 m。他想让你找一个长度为 n 的正整数序列 a，满足以下两个条件：
- 序列是“有趣的”：对于序列中的任意一个元素
a_i，所有严格小于a_i的元素的按位异或和（Bitwise XOR）为 0。 - 序列的和为
m：序列中所有元素的总和等于m。
如果能找到这样的序列，就输出 "Yes" 和这个序列；如果找不到，就输出 "No"，的说。
举个栗子 🌰
序列
[1, 3, 2, 3, 1, 2, 3]是有趣的。为什么呢？- 对于元素
1，没有比它更小的元素，空集的异或和是0。 - 对于元素
2，比它小的元素是两个1，1 ⊕ 1 = 0。 - 对于元素
3，比它小的元素是两个1和两个2，1 ⊕ 1 ⊕ 2 ⊕ 2 = 0。 所以满足条件~
- 对于元素
序列
[1, 2, 3, 4]就不是有趣的。- 对于元素
2，比它小的元素是1，异或和是1，不等于0。所以这个序列就不乖，不是有趣的了喵。
- 对于元素
解题思路
这道题是要我们构造一个序列，而不是验证。对于这种“找任意一个解”的题目，我们通常可以尝试构造一个最最简单的结构，只要它满足条件就好啦，不需要想得太复杂哦。
简化“有趣”的条件
让我们先来研究一下“有趣”这个条件。对于序列中任意一个 a_i，所有比它小的元素的异或和都是 0。
这暗示了一个非常重要的性质：如果一个数 x 在序列中出现了，并且它不是序列中最小的数，那么 x 最好是成对出现的！不，是出现偶数次！
为什么呢？喵~ 假设序列里有 u_1 < u_2 < ... < u_k 这些不同的数值。
- 对于
u_2，所有比它小的元素就是所有的u_1。要让它们的异或和为0，那么u_1的个数必须是偶数。（u_1 ⊕ u_1 ⊕ ... (偶数次) = 0） - 对于
u_3，所有比它小的元素是所有的u_1和u_2。我们已经知道u_1的异或和是0了，所以为了让总异或和为0，u_2的个数也必须是偶数。 - 以此类推，除了序列中最大的那个数值，其他所有数值的出现次数都必须是偶数次！
这个发现太棒啦！我们可以利用这个性质来构造我们的序列。最简单的构造方法就是让大部分元素都一样，比如都设为 1。
分情况讨论
情况一：n 是奇数
当 n 是奇数时，我们可以让前 n-1 个数都是 1。因为 n-1 是一个偶数，所以我们有偶数个 1。
- 序列的前
n-1项：1, 1, ..., 1 - 它们的和是
n-1。 - 为了让总和为
m，最后一个数a_n就必须是m - (n-1)。
我们来检查一下这个构造是否满足条件：
- 所有数都得是正整数。所以
m - (n-1) >= 1，也就是m >= n。如果m < n，n个正整数的和至少是n，肯定凑不出m，所以无解。 - 序列是否有趣？
- 如果
m - (n-1) = 1，那么所有数都是1，当然有趣。 - 如果
m - (n-1) > 1，那么序列里有两种数：1和m-(n-1)。1是较小的数，它出现了n-1次（偶数次）。- 对于元素
1，没有比它小的数，异或和0，OK。 - 对于元素
m-(n-1)，比它小的数是n-1个1，它们的异或和是0，也OK。
- 对于元素
- 如果
所以，当 n 是奇数时：
- 如果
m < n，输出 "No"。 - 如果
m >= n，输出 "Yes"，然后输出n-1个1和一个m - (n-1)。
情况二：n 是偶数
当 n 是偶数时，如果我们还用上面的方法，构造 n-1 个 1，那么 n-1 就是奇数了。这样一来，对于比 1 大的数，它看到的 1 的异或和就是 1，不满足条件了，喵呜~
我们得换个思路。根据我们之前的分析，如果 n 是偶数，那么序列中所有种类的数（包括最大值）都必须出现偶数次，这样才能保证总个数是偶数。
- 如果每个数
v都出现偶数次c_v，那么它对总和的贡献c_v * v一定是偶数。 - 所以，总和
m必然是所有这些偶数的和，结果也一定是偶数！
所以我们得出了一个关键结论：如果 n 是偶数，那么 m 必须也是偶数，否则无解！
好，那如果 n 和 m 都是偶数呢？我们可以这样构造：
- 让前
n-2个数都是1。n-2是一个偶数，所以我们有偶数个1。 - 它们的和是
n-2。 - 剩下的和是
m - (n-2)，我们需要用两个数来凑。为了满足“成对出现”的原则，最简单的就是让这两个数相等！ - 所以最后两个数都是
(m - (n-2)) / 2。
我们来检查一下这个构造：
- 所有数都得是正整数。
m和n都是偶数，所以m - (n-2)也是偶数，可以被2整除。- 我们需要
(m - (n-2)) / 2 >= 1，即m - n + 2 >= 2，也就是m >= n。和奇数情况一样，这是个基本要求。
- 序列是否有趣？
- 设
x = (m - (n-2)) / 2。 - 如果
x=1，所有数都是1，总共n个（偶数个），OK。 - 如果
x>1，序列里有两种数：1和x。1出现了n-2次（偶数次），x出现了2次（偶数次）。所有数都出现了偶数次，这个序列肯定是有趣的！
- 设
所以，当 n 是偶数时：
- 如果
m < n或者m是奇数，输出 "No"。 - 如果
m >= n并且m是偶数，输出 "Yes"，然后输出n-2个1和两个(m - (n-2)) / 2。
总结一下我们的策略，是不是清晰多啦？喵~
代码实现
下面就是根据上面的思路写出的 C++ 代码啦，主人可以参考一下哦。
#include <iostream>
#include <vector>
#include <numeric>
void solve() {
long long n, m;
std::cin >> n >> m;
// n 个正整数的和至少为 n，如果 m < n 就不可能啦
if (n > m) {
std::cout << "No\n";
return;
}
// 情况一：n 是奇数
if (n % 2 != 0) {
std::cout << "Yes\n";
// 前 n-1 个数都设为 1
for (int i = 0; i < n - 1; ++i) {
std::cout << "1 ";
}
// 最后一个数补足总和
std::cout << m - (n - 1) << "\n";
} else { // 情况二：n 是偶数
// 如果 n 是偶数，m 必须也是偶数
if (m % 2 != 0) {
std::cout << "No\n";
} else {
std::cout << "Yes\n";
// 计算最后两个相等数的值
long long val = (m - (n - 2)) / 2;
// 前 n-2 个数都设为 1
for (int i = 0; i < n - 2; ++i) {
std::cout << "1 ";
}
// 最后两个数是 val
std::cout << val << " " << val << "\n";
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点小课堂
这道题虽然是构造题，但也涉及了一些有趣的知识点呢！
按位异或 (Bitwise XOR)
- 这是计算机中的一种二进制运算，符号是
^(C++/Java) 或xor(Python)。 - 它的法则是：相同为
0，不同为1。 - 它有几个超级有用的性质，是解题的关键喵：
x ^ x = 0(任何数和自己异或都等于0)x ^ 0 = x(任何数和0异或都等于它自己)a ^ b = b ^ a(交换律)a ^ (b ^ c) = (a ^ b) ^ c(结合律)
- 因为
x ^ x = 0，所以偶数个相同的数异或起来结果是0，奇数个相同的数异或起来结果是它本身。
- 这是计算机中的一种二进制运算，符号是
构造思想 (Constructive Algorithms)
- 当题目要求你找到“任何一个”满足条件的解时，通常不需要去寻找所有可能的解，或者一个特别复杂的解。
- 最好的策略是“化繁为简”，尝试构造一个结构最简单的解。
- 在这道题里，我们把大部分元素都设为
1，就是这种思想的体现。这大大降低了我们分析问题的难度。
奇偶性分析 (Parity Analysis)
- 分析问题中数量的奇偶性，是数论和组合问题中一个非常强大的工具！
- 在本题中，我们通过分析元素出现的次数必须是偶数，从而推断出当
n为偶数时，总和m也必须是偶数。这个小小的发现直接帮我们排除了一半的无解情况，是不是很神奇，喵~
好啦，今天的题解就到这里啦！希望本喵的讲解对主人有帮助哦。如果还有不懂的地方，随时可以再来问我！喵~ ✨