牛客周赛 Round 127 里这道 Carry The Bit题面看着挺朴素给一个位数 n 和一个非负整数 k问有多少个有序数对 (a,b) 满足 0≤a,b2^n而且 ab 在二进制竖式加法里恰好产生 k 次进位。题目名里的 carry 本身就是“进位”的意思可以理解成双关到底是“带着这个 bit 走”还是“这个位产生了进位”读完题基本就确定了是后者。这类题我在赛后复盘时通常愿意多写几句因为它特别适合用来练一种很常见的竞赛套路——按位 DP。如果你之前只熟悉高位往低位枚举的数位 DP碰到这道题十有八九会卡住一旦转过弯来代码反而短得让人怀疑自己是不是写漏了。这篇文章会从暴力开始推演把状态怎么来、转移怎么写、坑在哪全部过一遍顺便给一份可以直接提交的 C 和 Python 代码。适合正在补位运算计数题的新手也适合想把这题整理进自己板子库的选手。1. 题目理解与第一步工作1.1 题面还原与“进位次数”的定义先复述一下题意因为“进位次数”这个说法有时候会产生歧义。所谓一次进位指的是在某一位上做加法时三个数a 的这一位、b 的这一位、来自低位的进位加起来大于等于 2于是要向高一位进 1。比如 112最低位产生了一次进位11(3) 01(1) 100(4) 时最低位 112 产生进位然后十位 011低位的进位又等于 2再产生一次进位所以总共是 2 次进位。也就是说每一次“sum 2”就是一个独立的进位事件我们要统计的是一共有多少个这样的位置。接收一个从低位传来的进位本身不算“产生进位”。这个定义在后面写代码时会直接决定 cnt 到底累加什么很多人 WA 就是栽在这上面。题目统计的是有序对也就是说 (0,1) 和 (1,0) 算两种不同的方案。这一点在赛场上也要注意有些题会问无序对改的时候只需要最后处理一下对称性但状态设计基本不用动。1.2 暴力枚举到底有多慢如果你第一次看到这题想的是“直接枚举所有 a 和 b”其实方向不算错但复杂度直接爆炸。可选的数对一共有 2^n × 2^n 4^n 个每一对都要把 n 位做一遍竖式加法总复杂度是 O(n × 4^n)。感觉一下这个数字n10 的时候4^10 ≈ 100 万还能跑n15 的时候是 4^15 ≈ 10 亿已经要等半天n20 的时候 4^20 ≈ 1.1 万亿完全不可行。而牛客周赛这种题 n 给个 100 都很正常甚至更大。所以暴力只能用来写对拍绝对不能当正解。那问题就变成了既然无法枚枚举每一个具体的 a 和 b我们能不能把 n 位拆开一位一位地统计答案是可以因为二进制加法的进位规则很简单每一层只需要知道当前两个数位和来自低位的进位完全感受不到 a 和 b 的完整值。1.3 一个方向问题进位是从低位流向高位的这是整道题最关键的思维拐点。平时做数位 DP比如统计小于等于某个上界的数字个数我们习惯从高位往低位枚举因为这样才能利用“前缀相同当前位小于上界”这个条件。但这题的情况完全不同进位只能从低位传到高位。如果你想从高位往低位做处理当前位时你根本不知道低位是否会递一个进位上来而这个进位会直接改变当前位的加法结果于是后续状态全部乱掉。所以这题必须反着来从最低位开始逐位往高位转移。做这种“从低到高”的按位 DP 时最高位的处理尤其要注意因为最高位仍然可能产生一个进位那个进位会变成结果的一位但它并不是“传递给更高位的进位”不能计数。也就是说最终答案要取“处理完 n 位后当前进位为 0”的那些方案数。2. 核心算法低位往高位的数位 DP2.1 状态定义dp[carry][cnt] 到底代表什么既然从低位往高位做我们只要维护两个信息就够了当前向高位的进位值 carry以及到目前为止已经产生的进位次数 cnt。用 dp[carry][cnt] 表示“已经固定完低位的若干位当前进位是 carry累计进位次数是 cnt”的方案数。初始状态是 dp[0][0] 1因为最低位开始之前没有任何低位给它进位累计进位次数当然也是 0。有些选手喜欢写成 dp[pos][carry][cnt] 的三维数组其实 pos 这一维没必须保留我们本来就是从低到高逐层更新的每一层只依赖上一层的状态直接滚动掉即可。滚动之后空间变成 O(2 × (k1))非常小。这里“方案数”的含义要理解清楚它不关心 a 和 b 的具体大小只关心每一位的 01 选择。第 i 位 a 的取值是 0 或 1b 的取值是 0 或 1这两者的选择会唯一确定一条路径。不同的数对 (a,b) 一定对应不同的按位选择序列所以统计方案数就是统计满足条件的数对数量不会重复也不会漏掉。2.2 状态转移三输入的二进制全加器处理到某一位时我们手上有三个输入a 的这一位 bab 的这一位 bb以及来自低位的进位 carry_in。这三个数加起来结果有两种输出本位的和 s以及向高位的进位 carry_out。把 ba、bb、carry_in 的所有组合列出来其实就是一个标准的全加器真值表babbcarry_insum本位和 scarry_out000000001110010110011201100110101201110201111311虽然这里 sum 最大只有 3但用公式表达会更通用sum ba bb carry_in本位和是 sum 1进位数是 sum 2。如果喜欢逻辑表达式也可以写成 carry_out (ba bb) | (ba carry_in) | (bb carry_in)和表格完全等价。转移的时候枚举 ba 和 bb 的四种组合计算出新的进位 ncarry再计算出新的累计次数 ncnt cnt ncarry。只有当 ncnt k 时才把方案数累加到下一层。注意这里累加的是 ncarry也就是这一位“新产生”的进位而不是来自低位的 carry_in。carry_in 只是继承下来的状态它不应该被加进 cnt。2.3 复杂度与正确性复杂度很容易算每一层要枚举 carry2 种、cntk1 种、ba2 种、bb2 种所以一层是 O(4k)总复杂度 O(4nk)。n100、k100 时只有 4 万次基本操作对竞赛来说几乎可以忽略。空间方面滚动二维数组是 O(2(k1))就算 n 开到 1e5只要 k 不大也没有压力。正确性可以从“唯一路径”的角度来看任意一个有序对 (a,b)把它从低位到高位拆开每一位的两个 bit 会跟着一个确定的进位状态一路走完 n 层并在最后给出一个确定的累计进位次数。也就是说每一种满足 cntk 的路径都对应若干个数对而且这些路径互不相交。DP 本质上就是把 4^n 条路径压缩成若干个状态完成的统计既没有重复也没有遗漏。3. 完整实现与代码讲解3.1 C 实现代码不长核心就是滚动数组和四层循环。完整实现如下#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; while (cin n k) { // dp[carry][cnt] vectorvectorlong long dp(2, vectorlong long(k 1, 0)); vectorvectorlong long ndp(2, vectorlong long(k 1, 0)); dp[0][0] 1; for (int pos 0; pos n; pos) { for (auto row : ndp) fill(row.begin(), row.end(), 0); for (int carry 0; carry 2; carry) { for (int cnt 0; cnt k; cnt) { long long cur dp[carry][cnt]; if (cur 0) continue; for (int ba 0; ba 2; ba) { for (int bb 0; bb 2; bb) { int sum ba bb carry; int ncarry (sum 2) ? 1 : 0; int ncnt cnt ncarry; if (ncnt k) { ndp[ncarry][ncnt] cur; if (ndp[ncarry][ncnt] MOD) ndp[ncarry][ncnt] - MOD; } } } } } dp.swap(ndp); } cout dp[0][k] % MOD \n; } return 0; }开头处理了多组测试数据因为牛客这类周赛经常是一个文件里跑很多个 case。每组数据开始前dp 数组重新初始化为全 0再把 dp[0][0] 设为 1。这里的小优化是因为 ncarry 只能是 0 或 1所以 ndp 第一维只有 2第二维是 k1。取模时用了先加再判减的方式比% MOD快一些在 n 大时能省不少时间。输出的答案取dp[0][k]这一点比较容易被新手漏掉。最高位处理完以后如果当前进位是 1说明结果会多出一位但这个多出的一位不是一次“传递出去的进位”不能计入 cnt。满足条件的方案只可能是处理完 n 位之后进位正好归零的那些所以dp[0][k]才是答案。3.2 Python 实现Python 写起来思路完全一样只是把循环和取模写得更直白一些import sys MOD 10**9 7 def solve(): input_data sys.stdin.read().strip().split() it iter(input_data) out_lines [] for n_str, k_str in zip(it, it): n, k int(n_str), int(k_str) dp [[0] * (k 1) for _ in range(2)] dp[0][0] 1 for _ in range(n): ndp [[0] * (k 1) for _ in range(2)] for carry in range(2): for cnt in range(k 1): cur dp[carry][cnt] if cur 0: continue for ba in (0, 1): for bb in (0, 1): s ba bb carry ncarry 1 if s 2 else 0 ncnt cnt ncarry if ncnt k: ndp[ncarry][ncnt] (ndp[ncarry][ncnt] cur) % MOD dp ndp out_lines.append(str(dp[0][k] % MOD)) print(\n.join(out_lines)) if __name__ __main__: solve()Python 版本直接用% MOD取模写法更安全省心。如果输入量很大用sys.stdin.read().split()一次性读进来会比逐行读更快。枚举 ba 和 bb 时的(0, 1)元组在循环里会反复创建其实可以直接写range(2)再组合但是两种写法性能差距可以忽略可读性更好就行。3.3 小规模暴力对拍与样例验证写 DP 题最忌讳“感觉对了就交”。我一般会先写一个暴力函数专门用来对拍小数据。这里的暴力可以直接模拟竖式加法def count_carries(a, b): carry 0 cnt 0 while a 0 or b 0 or carry 0: s (a 1) (b 1) carry if s 2: cnt 1 carry 1 else: carry 0 a 1 b 1 return cnt用这个函数去枚举 n2 的所有情况能做一个小规模的正确性验证。当 n2 时a 和 b 都从 0 取到 3一共 16 个有序对。人工梳理进位次数可以发现进位次数为 0 的有 9 个进位次数为 1 的有 4 个分别是 (1,1)、(2,2)、(2,3)、(3,2)进位次数为 2 的有 3 个分别是 (1,3)、(3,1)、(3,3)。所以对于输入2 1答案应该是 4。拿上面的 DP 代码跑一下输出正好是 4。再测一组更小的n1 时只有 (1,1) 会产生一次进位所以1 0答案是 31 1答案是 1程序也能正确输出。对拍这一步在本地几秒钟就能完成但能帮你挡掉很多莫名其妙的 WA。4. 常见错误与排查实录4.1 从高位往低位 DP状态根本递推不动我猜大多数第一次做这道题的人第一反应都会写“从小到大枚举位置”但真正动手时手却很诚实地按数位 DP 的习惯从高位开始。从高位处理的直接后果是处理到第 i 位时你无法确定第 i-1 位会不会给第 i 位进位因为低位还没有被固定。有些人想靠“多开一维状态记未来会不会进位”来弥补结果状态直接膨胀到指数级还不如暴力。正确做法就是前面反复强调的从低位往高位转移。如果你在赛场上发现自己的 DP 写着写着需要“预知”后面的选择大概率就是方向反了。4.2 进位计数到底记在哪一位另一个常见坑是把“接收到的进位”也当成了新增的进位。比如当前 carry_in 1但这一位 a 和 b 都是 0那么本位结果是 1没有向更高位产生新的进位cnt 不应该增加。如果写成cnt carry_in最后答案会偏大。判断标准很简单只有sum ba bb carry_in 2时才说明这一位产生了进位此时才能把 ncarry 累加进 cnt。carry_in 只是状态的一部分不是计数对象。这个坑在真值表里非常清楚但脱离纸面写代码时特别容易手滑。4.3 取模、long long 和数组初始化答案要对 1e97 取模这个大家都记得但有两个细节容易被忽略。第一如果不注意 C 中 dp 的累加可能在极端数据下溢出。虽然每次累加都会做取模但ndp[ncarry][ncnt] cur这一句两边都已经是小于 MOD 的数加完最多 2e914int 范围 2.1e9 左右非常接近上限所以最稳的做法是直接用 long long这也是我代码里用long long的原因。第二多组数据时 ndp 每层必须清空。我习惯每层循环开头用fill把 ndp 全部置零这个操作如果漏了上一层的残留值会影响下一层的答案而且这种 bug 通常只在多组数据时出现本地单测还测不出来特别恶心。4.4 卡在“恰好 k 次”的边界条件如果题目把 k 给到和 n 一样大甚至更大虽然正常不会边界处理也要小心。我们的数组第二维是 k1转移时只有当ncnt k才累加所以 k 再大也只会让数组变大不会越界。但如果 k 很小比如 k0那么所有产生进位的位置都必须被放弃只有完全无进位的数对能被统计进来代码逻辑依然正确只是要注意初始化时 dp 数组第二维只有 1 个有效位置别越界。5. 变题思路与赛后复盘5.1 改成“至少 k 次”或者“求期望”如果题目从“恰好 k 次”变成“至少 k 次”最简单的处理是在 DP 统计结束时改成对dp[0][cnt]中所有 cnt k 的项求和。也可以直接把 DP 状态里的 cnt 维度截断到 k也就是当累计次数超过 k 时统一归入 k表示“已经超过阈值”。这两种方法都能在 O(nk) 内解决第二种对状态维度的控制更彻底后续想再改回“恰好”也更方便。如果题目要求的是所有数对的进位次数总和那就把记录“个数”的 DP 改造成记录“个数 和”的形式每个状态多维护一个 sum转移时旧的贡献照搬新的贡献加上 cur×ncarry。这种“双维护”技巧在计数题里很常用原理类似于树形 DP 里同时维护数量与权值和。5.2 加上上下界限制数位 DP 的进阶形态如果题目改成统计某个区间范围内的数对比如 a∈[L1,R1]b∈[L2,R2]那就真的是经典数位 DP 了。需要把区间拆成前缀差分然后同时对两个数做上下界限制。不过因为进位要从低位往高位走而上下界比较通常从高位往低位判断两个方向撞在一起直接做会非常难受。我自己遇到这种题时会考虑两条路一是把二进制位从低位到高位处理同时用类似“已知低位反推高位范围”的思路做这个写起来复杂但本质上还是这个全加器模型只是每一层要维护的信息从 carry、cnt 变成了 carry、cnt、a 是否贴上界、a 是否贴下界、b 是否贴上界、b 是否贴下界。二是用自动机把上下界约束建模到每一位的合法选择集合里再跑同样的扫描。无论哪条路状态都比原题膨胀不少适合当作这个模型的进阶练习题不建议在周赛里现场硬推。5.3 竞赛里的时间分配建议说说周赛现场的策略。像 Carry The Bit 这种“题意清晰、状态经典”的题属于整个比赛里必须拿下的分它不应该排到压轴题的位置。我打这场的时候第一眼没想出来直接在纸上画了一个竖式加法从右往左画了一个箭头脑子里立刻就冒出了状态的定义。如果你也卡在暴力思路上我的建议是先别急画一个三行两列的竖式把低位到高位的方向标出来再把“当前从低位拿到的进位”和“当前要向高位送出的进位”分开写状态基本就自己出来了。赛后我会把这类题整理进位运算计数专题和数位DP的上下界版本、矩阵快速幂版本串成一条知识线。这次这道题虽然代码不到四十行但“方向决定状态状态决定复杂度”这个点值得反复琢磨。
