企业官网建设流程全解析

牛客周赛 Round 127 里这道 Carry The Bit，题面看着挺朴素：给一个位数 n 和一个非负整数 k，问有多少个有序数对 (a,b) 满足 0≤a,b<2^n，而且 a+b 在二进制竖式加法里恰好产生 k 次进位。题目名里的 carry 本身就是“进位”的意思，可以理解成双关：到底是“带着这个 bit 走”，还是“这个位产生了进位”，读完题基本就确定了是后者。

这类题我在赛后复盘时通常愿意多写几句，因为它特别适合用来练一种很常见的竞赛套路——按位 DP。如果你之前只熟悉高位往低位枚举的数位 DP，碰到这道题十有八九会卡住；一旦转过弯来，代码反而短得让人怀疑自己是不是写漏了。这篇文章会从暴力开始推演，把状态怎么来、转移怎么写、坑在哪全部过一遍，顺便给一份可以直接提交的 C++ 和 Python 代码。适合正在补位运算计数题的新手，也适合想把这题整理进自己板子库的选手。

1. 题目理解与第一步工作

1.1 题面还原与“进位次数”的定义

先复述一下题意，因为“进位次数”这个说法有时候会产生歧义。所谓一次进位，指的是在某一位上做加法时，三个数（a 的这一位、b 的这一位、来自低位的进位）加起来大于等于 2，于是要向高一位进 1。比如 1+1=2，最低位产生了一次进位；11(3) + 01(1) = 100(4) 时，最低位 1+1=2 产生进位，然后十位 0+1+1（低位的进位）又等于 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)。

感觉一下这个数字：n=10 的时候，4^10 ≈ 100 万，还能跑；n=15 的时候是 4^15 ≈ 10 亿，已经要等半天；n=20 的时候 4^20 ≈ 1.1 万亿，完全不可行。而牛客周赛这种题 n 给个 100 都很正常，甚至更大。所以暴力只能用来写对拍，绝对不能当正解。

那问题就变成了：既然无法枚枚举每一个具体的 a 和 b，我们能不能把 n 位拆开，一位一位地统计？答案是可以，因为二进制加法的进位规则很简单，每一层只需要知道当前两个数位和来自低位的进位，完全感受不到 a 和 b 的完整值。

1.3 一个方向问题：进位是从低位流向高位的

这是整道题最关键的思维拐点。

平时做数位 DP，比如统计小于等于某个上界的数字个数，我们习惯从高位往低位枚举，因为这样才能利用“前缀相同，当前位小于上界”这个条件。但这题的情况完全不同：进位只能从低位传到高位。如果你想从高位往低位做，处理当前位时你根本不知道低位是否会递一个进位上来，而这个进位会直接改变当前位的加法结果，于是后续状态全部乱掉。

所以这题必须反着来，从最低位开始，逐位往高位转移。做这种“从低到高”的按位 DP 时，最高位的处理尤其要注意，因为最高位仍然可能产生一个进位，那个进位会变成结果的一位，但它并不是“传递给更高位的进位”，不能计数。也就是说，最终答案要取“处理完 n 位后当前进位为 0”的那些方案数。

2. 核心算法：低位往高位的数位 DP

2.1 状态定义：dp[carry][cnt] 到底代表什么

既然从低位往高位做，我们只要维护两个信息就够了：当前向高位的进位值 carry，以及到目前为止已经产生的进位次数 cnt。

用 dp[carry][cnt] 表示“已经固定完低位的若干位，当前进位是 carry，累计进位次数是 cnt”的方案数。初始状态是 dp[0][0] = 1，因为最低位开始之前，没有任何低位给它进位，累计进位次数当然也是 0。

有些选手喜欢写成 dp[pos][carry][cnt] 的三维数组，其实 pos 这一维没必须保留，我们本来就是从低到高逐层更新的，每一层只依赖上一层的状态，直接滚动掉即可。滚动之后空间变成 O(2 × (k+1))，非常小。

这里“方案数”的含义要理解清楚：它不关心 a 和 b 的具体大小，只关心每一位的 01 选择。第 i 位 a 的取值是 0 或 1，b 的取值是 0 或 1，这两者的选择会唯一确定一条路径。不同的数对 (a,b) 一定对应不同的按位选择序列，所以统计方案数就是统计满足条件的数对数量，不会重复也不会漏掉。

2.2 状态转移：三输入的二进制全加器

处理到某一位时，我们手上有三个输入：a 的这一位 ba，b 的这一位 bb，以及来自低位的进位 carry_in。这三个数加起来，结果有两种输出：本位的和 s，以及向高位的进位 carry_out。

把 ba、bb、carry_in 的所有组合列出来，其实就是一个标准的全加器真值表：

虽然这里 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 复杂度与正确性

复杂度很容易算：每一层要枚举 carry（2 种）、cnt（k+1 种）、ba（2 种）、bb（2 种），所以一层是 O(4k)，总复杂度 O(4nk)。n=100、k=100 时只有 4 万次基本操作，对竞赛来说几乎可以忽略。空间方面滚动二维数组是 O(2(k+1))，就算 n 开到 1e5，只要 k 不大也没有压力。

正确性可以从“唯一路径”的角度来看：任意一个有序对 (a,b)，把它从低位到高位拆开，每一位的两个 bit 会跟着一个确定的进位状态一路走完 n 层，并在最后给出一个确定的累计进位次数。也就是说，每一种满足 cnt=k 的路径都对应若干个数对，而且这些路径互不相交。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] vector<vector<long long>> dp(2, vector<long long>(k + 1, 0)); vector<vector<long long>> ndp(2, vector<long 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，第二维是 k+1。取模时用了先加再判减的方式，比% 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

用这个函数去枚举 n=2 的所有情况，能做一个小规模的正确性验证。

当 n=2 时，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。再测一组更小的：n=1 时，只有 (1,1) 会产生一次进位，所以1 0答案是 3，1 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 和数组初始化

答案要对 1e9+7 取模，这个大家都记得，但有两个细节容易被忽略。

第一，如果不注意 C++ 中 dp 的累加可能在极端数据下溢出。虽然每次累加都会做取模，但ndp[ncarry][ncnt] += cur这一句，两边都已经是小于 MOD 的数，加完最多 2e9+14，int 范围 2.1e9 左右，非常接近上限，所以最稳的做法是直接用 long long，这也是我代码里用long long的原因。

第二，多组数据时 ndp 每层必须清空。我习惯每层循环开头用fill把 ndp 全部置零，这个操作如果漏了，上一层的残留值会影响下一层的答案，而且这种 bug 通常只在多组数据时出现，本地单测还测不出来，特别恶心。

4.4 卡在“恰好 k 次”的边界条件

如果题目把 k 给到和 n 一样大，甚至更大（虽然正常不会），边界处理也要小心。我们的数组第二维是 k+1，转移时只有当ncnt <= k才累加，所以 k 再大也只会让数组变大，不会越界。但如果 k 很小，比如 k=0，那么所有产生进位的位置都必须被放弃，只有完全无进位的数对能被统计进来，代码逻辑依然正确，只是要注意初始化时 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的上下界版本、矩阵快速幂版本串成一条知识线。这次这道题虽然代码不到四十行，但“方向决定状态，状态决定复杂度”这个点，值得反复琢磨。