“不点两面”是牛客每日一题系列里一个很有意思的题我第一次看到这个名字还以为是麻将或者扑克牌规则点开才发现它其实是一道非常典型的“相邻位置限制计数”问题。题干本身就一句话一排有 n 个位置每个位置可以取 0 或者 1但是不能让两个相邻的位置同时取 1。也就是“点了一面旁边那一面就不能再点”名字起得还挺形象。这道题有一个 hard version核心区别就是 n 的规模从 1e5 级别直接拉到了 1e18 级别逼着你把 O(n) 的递推优化成 O(log n)。很多人第一眼会觉得这不是套个循环就完了吗结果一看数据范围直接卡死。这篇就把从朴素 DP 到矩阵快速幂的全过程拆开讲清楚顺便聊聊怎么用牛客的每日一题 tracker 把这类题吃透。1. 题目拆解到底在数什么1.1 约束条件与“不点两面”的名字来源先明确题面。假设我们有一个长度为 n 的序列每个位置只能是 0 或者 1。其中 1 表示“点”0 表示“不点”。合法的序列必须满足任意相邻两个位置不能同时为 1。换句话说010 合法101 合法000 合法011 不合法因为位置 2 和位置 3 都是 1相邻了110 不合法位置 1 和位置 2 相邻111 更不合法出现了两组相邻 1。“不点两面”这个描述其实就是在说“相邻的两个格子亮了一面另一面就得灭着”。这种序列在组合数学里有个对应的名字不含连续 1 的 01 串。需要数的是在所有 2^n 种可能序列里有多少个是合法的。并且结果要对一个模数取余常见的牛客题会取 998244353。这道题的答案并不是什么冷门结论它恰好是斐波那契数列的亲戚。n1 时答案是 2n2 时答案是 3n3 时答案是 5后面分别是 8、13、21……看出规律了吧其实就是斐波那契数列从 2 开始往后排。这里也提醒一句不要一看到“斐波那契”就开始套通项公式。hard version 里 n 可以到 1e18直接迭代或者递归都会炸通项公式里带了根号 5 和浮点数取模精度又是个坑。真正稳妥的做法是矩阵快速幂这也是本文的重点。1.2 为什么题目要分成 easy 和 hard 两个版本很多 OJ 上的题都会给两个版本比如 CF 的 Div2 题、牛客的每日一题也喜欢搞 easy version 和 hard version。easy version 通常用来让你理解题意和写出朴素解法hard version 则是在同一套逻辑上把规模调大逼你换工具。在这道题里easy versionn ≤ 1e5开一个 dp 数组甚至不需要滚动数组O(n) 直接过。hard versionn ≤ 1e18O(n) 是不可能跑完的必须把递推关系矩阵化用快速幂把复杂度降到 O(log n)。我之前见过不少同学刷题的时候只写 easy 版本看到 hard version 直接被吓退觉得“这不是同一道题吗怎么数据范围差这么多”。其实 hard version 并不是题目变难了而是引导你发现“线性递推 大整数幂”这个组合的通用解决方案。把这一题吃透很多状态压缩 DP 的快速幂优化题你都能顺手写出来。2. 朴素 DP一眼看穿递推关系2.1 状态定义与转移方程在做任何优化之前先把朴素 DP 写明白。我们可以定义两个状态dp[i][0]长度为 i 的合法序列中第 i 个位置取 0 的方案数dp[i][1]长度为 i 的合法序列中第 i 个位置取 1 的方案数。转移关系其实非常直观如果第 i 个位置取 0那么第 i-1 个位置取 0 或者取 1 都可以所以 dp[i][0] dp[i-1][0] dp[i-1][1]。如果第 i 个位置取 1那么第 i-1 个位置绝对不能取 1只能取 0所以 dp[i][1] dp[i-1][0]。边界条件也简单dp[1][0] 1序列只有“0”这一种dp[1][1] 1序列只有“1”这一种。最终答案就是 dp[n][0] dp[n][1]。如果你把总方案数单独记作 f[n] dp[n][0] dp[n][1]把它展开一下f[n] dp[n][0] dp[n][1] (dp[n-1][0] dp[n-1][1]) dp[n-1][0] f[n-1] dp[n-1][0]而 dp[n-1][0] dp[n-2][0] dp[n-2][1] f[n-2]所以f[n] f[n-1] f[n-2]这就是斐波那契递推。不过要注意起始项是 f[1] 2f[2] 3和标准斐波那契 F(1)1、F(2)1 错开了两个位置。如果你想让公式统一可以人为定义 f[0] 1此时 f[1] f[0] f[-1] 这种处理反而复杂不如直接矩阵从 n1 开始推。2.2 为什么 hard version 必须换思路如果 n 只有 1e5上面的 O(n) DP 完全够用。但是 n 到 1e18 以后这个循环是不可能跑完的。你感受一下这个数量级一个普通 CPU 每秒大约能执行 1e8 到 1e9 次简单运算。如果老老实实循环 1e18 次哪怕每次只做一次加法也要跑几十亿秒大约是几十年。更别提中间还夹杂取模、数组读写这些操作根本不可能在评测时限内出结果。所以 hard version 的关键不是把循环写得更快而是要找到一种“指数级减少计算次数”的方法。这里就轮到矩阵快速幂登场了。它的本质是既然每次递推都是同一个线性变换那连续做 n 次递推就等价于把同一个变换矩阵做 n 次幂。而一个 2×2 矩阵的幂可以用快速幂做到 O(log n)。3. 矩阵快速幂把 O(n) 压成 O(log n)3.1 从递推关系构造转移矩阵矩阵快速幂的第一步是把 DP 的状态转移写成矩阵乘法的形式。我们已经有了状态dp[i][1]第 i 位是 1dp[i][0]第 i 位是 0。把这两个状态放进一个列向量v[i] [ dp[i][1] ] [ dp[i][0] ]然后看从 i-1 到 i 的转移dp[i][1] 0 × dp[i-1][1] 1 × dp[i-1][0]dp[i][0] 1 × dp[i-1][1] 1 × dp[i-1][0]写成矩阵v[i] M × v[i-1]其中M [ 0 1 ] [ 1 1 ]验证一下M 的第一行乘 v[i-1]得到 dp[i][1]第二行乘 v[i-1]得到 dp[i][0]。没问题。初始向量是 v[1] [1; 1]对应 dp[1][1]1、dp[1][0]1。那么v[n] M × M × ... × M × v[1] M^(n-1) × v[1]所以问题转化为快速计算矩阵 M 的 n-1 次幂。最后答案就是 v[n] 两个元素之和ans v[n][0] v[n][1]也就是 M^(n-1) 这个矩阵乘上初始列向量 [1; 1] 之后两个分量的和。这里的核心思路值得再强调一遍线性递推关系一旦确定连续 n 次递推就是矩阵的 n 次幂。这个思路不止适用于斐波那契这一种题目所有形如 f[i] a×f[i-1] b×f[i-2] 的递推都可以套同一个转移矩阵模板。3.2 快速幂的原理指数减半运算量指数级下降很多人第一次接触快速幂会有点绕其实它和“二进制拆分”是同一个东西。我们要求 M^kk 是 n-1可能接近 1e18。如果挨个乘 k 次那回到刚才的问题。但快速幂的做法是先把 M 平方得到 M^2再平方得到 M^4再平方得到 M^8……每次指数翻倍只需要大约 60 次平方运算就能覆盖到 2^60而 2^60 已经超过 1e18 了。计算过程中把 k 转成二进制从低位到高位逐位检查。如果当前位是 1就把累乘结果乘上当前的矩阵如果当前位是 0就不用乘。但无论如何每次循环都要把底数矩阵自乘一次。这个过程用生活里的话说很像“合并同类项后再群发”。你有一个通知要发 1000 个人不会一个人一个人跑而是先建出 1、2、4、8、16……的名单组合再用二进制拼出 1000。这样只用了 10 次操作就完成了原本 1000 次才能完成的事。对于 2×2 矩阵一次乘法其实就是 8 次整数乘法和 4 次加法常数非常小。60 次循环下来性能开销可以忽略不计。3.3 边界条件千万别漏矩阵快速幂写出来以后最容易翻车的不是矩阵逻辑而是边界情况。n 0序列为空唯一合法的方案就是“空串”答案应该是 1。但矩阵公式默认 n≥1所以必须单独处理。n 1答案就是 2对应“0”和“1”。如果直接用 M^(0) × v[1]M^0 是单位矩阵算出来也是 2其实也行。但为了保险n≤1 的时候直接输出 1 或 2不要走到矩阵逻辑里去。很多同学的 hard version 代码在 n0 时输出 0或者 n1 时输出 1都是没想清楚“空序列也合法”这件事。这题隐蔽的坑就在这里。4. 完整实现C 与 Python 双版本4.1 C 代码注释版直接给出一个可以直接交的 C 版本。我用的是常见取模数 998244353如果题目给的是别的模数改一个常量就行。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 998244353; // 2x2 矩阵结构体 struct Mat { ll a[2][2]; // 构造函数flag 为 true 时构造单位矩阵 Mat(bool flag false) { memset(a, 0, sizeof(a)); if (flag) { a[0][0] 1; a[1][1] 1; } } }; // 矩阵乘法结果保存在返回矩阵里 Mat mul(const Mat x, const Mat y) { Mat z; for (int i 0; i 2; i) { for (int k 0; k 2; k) { if (x.a[i][k] 0) continue; // 小优化跳过 0 for (int j 0; j 2; j) { z.a[i][j] (z.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } } } return z; } // 矩阵快速幂base^exp Mat power(Mat base, ll exp) { Mat res(true); // 单位矩阵 while (exp 0) { if (exp 1) { res mul(res, base); } base mul(base, base); exp 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin n; if (n 0) { cout 1 \n; return 0; } if (n 1) { cout 2 \n; return 0; } // 转移矩阵 M Mat t; t.a[0][0] 0; t.a[0][1] 1; t.a[1][0] 1; t.a[1][1] 1; // 计算 M^(n-1) Mat pw power(t, n - 1); // 初始向量 v1 [1, 1]^T // 结果向量 pw * v1 ll s1 (pw.a[0][0] pw.a[0][1]) % MOD; // 第 n 位为 1 的方案数 ll s0 (pw.a[1][0] pw.a[1][1]) % MOD; // 第 n 位为 0 的方案数 ll ans (s1 s0) % MOD; cout ans \n; return 0; }这份代码的乘法循环里加了一个if (x.a[i][k] 0) continue;的小优化。对于 2×2 矩阵意义不大但它能让你在以后扩展到更大矩阵时少很多无效乘法建议保留这个习惯。关于取模MOD 约 9 亿多两个这样的数相乘结果小于 1e18long long 的最大值是 9.22e18所以直接乘不会溢出。只要不乱加很多个再取模这个写法是安全的。4.2 Python 实现的要点Python 写矩阵快速幂其实也很简洁而且 Python 的大整数天然免疫 int 溢出不需要像 C 那样担心乘法越界。缺点是常数大一点但 O(log n) 只有几十次矩阵乘法完全没问题。MOD 998244353 class Mat: def __init__(self, a110, a120, a210, a220): self.a11 a11 self.a12 a12 self.a21 a21 self.a22 a22 def mat_mul(x, y): return Mat( (x.a11 * y.a11 x.a12 * y.a21) % MOD, (x.a11 * y.a12 x.a12 * y.a22) % MOD, (x.a21 * y.a11 x.a22 * y.a21) % MOD, (x.a21 * y.a12 x.a22 * y.a22) % MOD, ) def mat_pow(base, exp): res Mat(1, 0, 0, 1) # 单位矩阵 while exp: if exp 1: res mat_mul(res, base) base mat_mul(base, base) exp 1 return res n int(input()) if n 0: print(1) exit() if n 1: print(2) exit() # 转移矩阵 [[0, 1], [1, 1]] trans Mat(0, 1, 1, 1) pw mat_pow(trans, n - 1) # 初始向量 [1, 1] s1 (pw.a11 pw.a12) % MOD s0 (pw.a21 pw.a22) % MOD print((s1 s0) % MOD)Python 版本里最容易踩的坑是n太大时递归调用矩阵快速幂用递归没问题但 Python 默认递归深度只有 1000好在指数二进制分解只需要 60 层不会爆。不过我还是推荐写成 while 循环省得哪天改成递归版本时踩坑。5. 实战经验常见坑和调试技巧5.1 问题排查速查表我刷题和给身边同学看代码时发现 hard version 的报错基本集中在下面几种情况。整理成表格方便你对照排查现象原因解决办法n0 输出 0没有考虑空序列也是合法方案明确题意后特判输出 1n1 输出 1忘了“单独一个 1”也是合法序列特判输出 2或者用初始向量 [1;1] 推答案和暴力 DP 对不上矩阵乘法的顺序写反了用列向量左乘矩阵结果是 v M × v不要写成 v × M中间结果出现负数某些写法在减法后没加 MOD每次运算后都做% MOD必要时加 MOD 再取余C 乘法结果异常或 AC 不了两个大数相乘溢出检查 MOD 是否超过 1e9超过则用 __int128 或快速乘超时矩阵乘法写成了三层 2×2 暴力还每次循环都取模多次优化循环顺序跳过 0减少冗余取模最隐蔽的一个坑是“矩阵传参顺序”。我见过一个同学代码里res mul(res, base)写成了res mul(base, res)结果 n 大一点答案全错。原因是矩阵乘法不满足交换律你从定义式v[i] M × v[i-1]推导出来的乘法顺序必须和代码保持一致。建议每一行代码都对照公式写注释。5.2 我的调试小习惯遇到这种递推类题目我从来不会直接拿大样例验证。比较好的流程是先写一个简单循环 DP处理 n 从 1 到 20 的答案输出出来。再用矩阵快速幂版本处理同样范围逐一对比。两边一致以后再提交 hard version。这种方法能帮你快速定位是转移矩阵写错了还是快速幂框架写错了。千万别一上来就对着 1e18 的样例调出错了根本不知道错在哪一步。我之前调试这类题时会手动展开前几项来验证。n1 答案 2n2 答案 3n3 答案 5n4 答案 8。如果你矩阵推出来的前几项是 2、3、5、8说明基础递推没写错如果第二项就是 4那多半是边界条件或者转移矩阵的行列弄反了。6. 从一道题到一套 tracker怎么用牛客每日一题搭刷题节奏6.1 牛客 tracker 的正确用法这道题出现在“牛客tracker / 每日一题”里很多人以为 tracker 就是个打卡记录每天做完打个勾就行。其实它更该被当成“错题本 思路索引”来用特别是 hard version 这种题你今天会做了两周后大概率又会忘记矩阵怎么构造。我的建议是记录时不要只写“AC了”而是填这几个字段日期题目难度核心思路耗时错点收获2025-01-15不点两面 hard中相邻限制 - 线性递推 - 矩阵快速幂40minn0 忘特判递推转矩阵的通用构造方法2025-01-16某人家的题中状态压缩 DP60min位运算优先级枚举子集的优化……………………………………这种表格比单纯打卡有价值得多。三个月后回头看你看到“错点”那一列就能回忆起自己当时踩过的坑。尤其是“n0 忘特判”这种第二次碰到大概率还会犯但表格会提醒你。6.2 这题能举一反三到什么程度矩阵快速幂不是只能用来做斐波那契。你可以试着把“不点两面”的限制改一改比如改成“任意两个 1 之间至少要隔两个 0”递推就会变成 f[i] f[i-1] f[i-3]这时候转移矩阵变成 3×3 的维度思路一模一样只是向量里需要多记一项。类似的场景还有2×n 的棋盘铺砖计数问题状态压缩后用矩阵快速幂优化带 k 个连续限制的计数问题用维度 k 的矩阵来刻画递推式是高阶线性递推时用多项式取模优化到 O(k^2 log n)。所以“不点两面”这道题虽然本身简单它是你进入“线性递推 快速幂”这个大类的一个入口。把这里面的矩阵构造吃透了后面写状态压缩 DP 的矩阵转移就不至于被 2^k 的维度吓住。我自己做题的习惯是每遇到一类新工具就用三四道不同场景的题去固定它。矩阵快速幂就是典型的“第一次写觉得别扭写到第三道就熟练”的东西。拿牛客每日一题里的递推题练手坚持一到两周再回头看“不点两面”的 hard version应该会觉得非常轻松。