洛谷-P1118 [USACO06FEB] Backward Digit Sums G/S 题解
题目链接：https://www.luogu.com.cn/problem/P1118
题目大意
给定一个正整数 $N$ 和最终的总和 sum，要求找出字典序最小的排列 a_1, a_2, ..., a_N（其中每个数字是 1 到 N 的一个排列），使得按照如下规则不断合并相邻两项，最后得到的唯一数字等于 sum：
- 每次将相邻两个数相加，生成长度减一的新序列；
- 重复此过程直到只剩一个数。
例如：
3 1 2 4
4 3 6
7 9
16
目标是从 N 和最终的 sum 反推出原始排列，并输出字典序最小的那个。若无解，则不输出任何内容。
核心观察：组合数学建模
这个过程本质上等价于 杨辉三角（Pascal's Triangle）的加权和。
为什么？
每个原始位置上的数在每一轮合并中会“传播”到下一层，其贡献次数恰好等于从顶部走到底部经过该位置的路径数
例如当 N=4 时，系数为：
- C(3,0)=1
- C(3,1)=3
- C(3,2)=3
- C(3,3)=1
但注意！上面例子中 3 1 2 4 → 16，而 3×1 + 1×3 + 2×3 + 4×1 = 3+3+6+4=16，完全吻合
解题策略
由于 N <= 12，全排列最多 12! 约等于 4.8 * 10^8，太大无法暴力枚举。
但我们可以使用 DFS + 剪枝 + 字典序优先搜索：
- 按字典序从小到大尝试每个位置填什么数字（1~N，不重复）；
- 在 DFS 过程中维护当前已选数字的加权和；
- 如果当前和已经超过
sum，直接剪枝； - 一旦找到第一个合法解（因为按字典序搜索），立即返回（保证字典序最小）。
这正是代码所采用的方法。
代码解析
1. 预处理组合数系数 k[i]
tmp[0] = 1;
tmp[1] = 1;
for (int i = 2; i <= n; i++) tmp[i] = i * tmp[i - 1]; // 阶乘
for (int i = 0; i < n; i++)
k[i] = tmp[n - 1] / tmp[n - 1 - i] / tmp[i]; // C(n-1, i)
计算每个位置的权重。
2. DFS 搜索（带状态压缩）
bool process(int flag, int index, int cur)
flag：位掩码，记录哪些数字已被使用（1-N对应bit:0-N-1）；index：当前要填第index个位置（0-indexed）；cur：当前加权和
递归终止条件：
index == n：所有位置填完，检查cur == sum。
剪枝：
- 若
cur > sum，提前返回 false（因为所有权重和数字都是正的，后续只会更大）。
尝试每个未使用的数字 i（1~N）：
- 设置
nums[index] = i； - 递归调用
process(flag | (1<<(i-1)), index+1, cur + i * k[index])； - 一旦某条路径成功，立即返回 true（保证字典序最小，因为 for 循环从小到大）。
3. 主函数：按字典序启动 DFS
for (int i = 1; i <= n; i++) {
nums[0] = i;
if (process(1 << (i - 1), 1, i * k[0])) {
flag = true;
break;
}
}
从第一个位置依次尝试 1,2,...,N，一旦找到解就停止，确保字典序最小。
正确性与复杂度
- 正确性：基于组合数加权模型 + 全排列搜索 + 剪枝。
- 时间复杂度：最坏情况仍是 O(N!)，但由于剪枝（
cur > sum提前退出）和 N <= 12，实际运行很快。 - 空间复杂度：O(N)，递归深度最多 12。
总结
本题的关键在于将多层相加过程转化为组合数加权和，从而将问题简化为带权重的排列搜索。通过 DFS + 状态压缩 + 剪枝 + 字典序优先，可以在合理时间内求解 N <= 12 的所有情况。
技巧总结：
- 杨辉三角系数 = 组合数 = 路径数 = 权重；
- 小规模排列问题可用 DFS + 位掩码；
- 字典序最小 ⇒ 从小到大枚举 + 找到即停；
- 剪枝：当前和超过目标值可提前退出。
