Leetcode题解故事

leetcode3336「算法竞技场 EP03」五大流派群殴 LeetCode 3336 实况直播吐血解说！

「算法竞技场 EP03」五大流派群殴 LeetCode 3336 实况直播吐血解说！

欢迎来到「算法竞技场」EP03！我是你们的主播——老白。先给错过前两期的观众补个课：EP01 我们围观了萌新被哈希圣光抬走，EP02 见证了四位选手在顺次数副本里花式炸鱼，难度曲线比我奶奶的血压还平稳。但今天，导演组直接空投了一颗数论炸弹——LeetCode 3336：最大公约数相等的子序列数量。

（弹幕：子序列 + GCD，这题明显是数学系派过来搞心态的卧底） （弹幕：老白你要是自己都没 AC 就来解说，我直接取关） （弹幕：前排出售花生瓜子枸杞保温杯，养生刷题从我做起）

任务简报

悬赏令：给你一个整数数组 nums，请你揪出所有满足下面条件的 非空子序列对 (seq1, seq2) 的数量：

  1. 互不侵犯条约——同一个下标，绝不能同时效忠 seq1 和 seq2。要么从一而终，要么当场弃权，脚踩两只船的直接火化。
  2. GCD 对齐协定——gcd(seq1) 必须精确等于 gcd(seq2)，谁大谁小都不行，必须一模一样。

答案请对 1e9+7 取模。数据规模：1 <= nums.length <= 200，1 <= nums[i] <= 200。

（弹幕：200？这不闭着眼暴力枚举？） （弹幕：楼上，200 个元素，每个元素 3 种选择 → 3^200，宇宙原子数才 10^80！） （弹幕：这就是传说中的「面善心黑」型 Hard，看着小，一动手就让你风扇唱歌） （弹幕：取模 1e9+7，标准防溢出姿势，我先给电脑磕个头）

任务摸底：这 BOSS 到底什么机制？

别急着冲上去送！在众神秀走位之前，咱先把 BOSS 的底牌摸清楚——面对数组里的每一个元素，你的操作面板上永远只有三个按钮：

  • 跳过——当它不存在，继续下一个。
  • 划给 seq1——把它丢进一号队伍，顺便用 gcd 重新算一下一号队伍的“最大公约光环”。
  • 划给 seq2——丢进二号队伍，同样刷新二号队的光环数值。

所以你从头扫到尾，其实是在爬一棵巨大的三叉决策树。这棵树的分支数约等于 3^n，当 n=200 时，如果真的一路莽穿，把所有叶子都踩一遍——别说什么服务器冒烟了，就算是赛博坦星球的硅基生命来了都得当场圆寂。

然而——你真的需要记住每一步选了哪些数字吗？答案是：大可不必。

这个 BOSS 最阴险的障眼法就在这里。任务只盯着最终结果：seq1 和 seq2 的最大公约数到底相不相等。而 gcd 这个函数，堪称算法界的终极摸鱼王：它只关心你当前塞进去的数和它手里已有的结果，对历史过程完全不关心。你把一堆数喂给它，它就懒洋洋地吐出一个新的 gcd，然后继续葛优躺，绝对不存日志。

（弹幕：gcd：我就是个无情的取模机器，别问我前面发生过什么） （弹幕：这哪是摸鱼，这是最高级的抽象！状态压缩懂不懂） （弹幕：这么说来，gcd 状态就是存档点？）

对头！既然 gcd 只认结果不认过程，那整个决策过程的“进度”就完全可以压缩成一个极简的存档状态：

( i , gcd1 , gcd2 ) 「已经处理完前 i 个元素，当前一号队的光环 = gcd1，二号队的光环 = gcd2」

整个状态空间有多大？i 最多 200，gcd1 和 gcd2 全都在 1 到 200 之间，总状态量撑死了几百万——当代电脑完全可以一口闷，不用怂。

（弹幕：好家伙，原来看似要踩遍宇宙，其实是个几百万格子的棋盘） （弹幕：所以这题本质是「如何高效遍历一张隐式状态图」） （弹幕：瞬间从玄学变科学了，我又觉得我行了）

接下来的所有打法，本质就是以不同姿势遍历这个状态图。有人正着走，有人倒着走，还有人直接把图给扬了。

先给大家透个底，今天出战的阵容，堪称算法界的复仇者联盟：“笨鸟先飞”历史积累 DP、“节能模式”滚动数组、“回头是岸”递归 DFS、“反转未来”期望 DP，以及最后一位神秘嘉宾——据说这位爷有数论界的瑞士军刀。

（弹幕：神秘嘉宾是什么鬼？？） （弹幕：我赌五毛，是莫比乌斯反演，刚刚瞄到弹幕有人在刷 μ 函数） （弹幕：不管是谁，今天能活下来的都是英雄）

瓜子饮料摆好，直播即将进入正赛环节。请把 「开卷」 打在公屏上，第一位选手，请登台！

一号选手·“笨鸟先飞”历史积累 DP

第一位选手缓步上台——他扶了扶眼镜：“大家好，我的信条就八个字——步步为营，笔笔入账。”

n = len(nums) 
m = max(nums)

# dp[i][j][k]：处理完前 i 个数，一号队 gcd=j，二号队 gcd=k 的方案数
dp = [[[0] * (m+1) for _ in range(m+1)] for _ in range(n+1)]

# 还没开始选，两支队伍都是空的，gcd 全是 0，有且仅有这一种开局
dp[0][0][0] = 1   

for i, num in enumerate(nums):
    # 每遇到一个新元素 num，就把之前所有可能的状态都翻出来，每种状态走三条路
    for j in range(m+1):
        for k in range(m+1):
            if dp[i][j][k] == 0: continue
            # 1. 不选
            dp[i+1][j][k] = (dp[i+1][j][k] + dp[i][j][k]) % MOD
            # 2. 放 seq1
            new_j = gcd(j, num)
            dp[i+1][new_j][k] = (dp[i+1][new_j][k] + dp[i][j][k]) % MOD
            # 3. 放 seq2
            new_k = gcd(k, num)
            dp[i+1][j][new_k] = (dp[i+1][j][new_k] + dp[i][j][k]) % MOD

# 最后把所有 gcd 相等且非空的格子累加起来
ans = sum(dp[n][g][g] for g in range(1, m+1)) % MOD

（弹幕：三维数组？内存要炸了吧？） （弹幕：这就是传说中的空间换时间，不对，是空间换头发） （弹幕：推送式 DP，老江湖了） （弹幕：所以每个 dp[i+1] 都被各种来源疯狂 +=，像在收红包）

老白解说：来，导播把镜头推近，咱们一起看看这位老实人的账本是怎么记的。

他的思路十分朴素：每遇到一个新元素，就把上一轮所有可能的状态全部翻出来，挨个问——“你要不要这个数？给 seq1 还是 seq2？"——然后把当前状态的方案数，一股脑儿推送到下一层对应的三个格子里。这套朴实无华的拳法，就是正向 DP，江湖人称历史积累 DP。核心就一句话：站在过去，推给未来。

好，现在把眼睛睁大，看到他满屏的 += 没有？(dp[i+1][j][k]=(dp[i+1][j][k]+...)%MOD) ——这可不是水字数，而是被逼出来的！因为下一层的一个目标格子，根本不是某一条路径的专属，它是个“众筹项目”！

就拿最终 gcd=2 这个格子来说吧，它可能从 (2, x) 选择不拿数，直接保送过来；也可能从 (4, x) 把数塞进 seq1，gcd 被压扁成 2 滑进来； (6, x)、(8, x)… 都能往这儿空投。每条来路都是一条合法路径，你要是敢用等号直接覆盖，就等于把其他路线的兄弟全踹下车，方案数就漏成筛子了。所以必须 +=，像收集七龙珠一样，来多少收多少，一条都漏不得。

等所有数都跑完，dp[n][g][g]（g ≥ 1）这些“两队光环相等且非空”的格子一加，答案就热乎乎地出炉了。复杂度嘛，时间 O(n·m²) 约八百万次运算，空间 O(n·m²) 稍显臃肿，但 n 和 m 最多200，当代 Python 轻松拿捏。

AC 图标第一次亮起！

（弹幕：八百万次循环加取模，Python 真的不会冒烟吗） （弹幕：实测不会，当代 CPU 表示这就跟热身操差不多） （弹幕：老实人 DP，面试写这个最稳，解释成本极低）

二号选手·“节能模式”滚动数组

一号刚下台，二号选手就跳了上来——他浑身上下挂满了「能源之星」认证贴纸：“前一个兄弟啥都好，就是太费内存了。看我的——空间压缩术！”

# 只需要一张当前表 dp，和一张临时表 new_dp
dp = [[0] * (m+1) for _ in range(m+1)]
dp[0][0] = 1

for num in nums:
    new_dp = [[0] * (m+1) for _ in range(m+1)]
    for j in range(m+1):
        for k in range(m+1):
            if dp[j][k] == 0: continue
            # 不选
            new_dp[j][k] = (new_dp[j][k] + dp[j][k]) % MOD
            # 放 seq1
            new_j = gcd(j, num)
            new_dp[new_j][k] = (new_dp[new_j][k] + dp[j][k]) % MOD
            # 放 seq2
            new_k = gcd(k, num)
            new_dp[j][new_k] = (new_dp[j][new_k] + dp[j][k]) % MOD
    dp = new_dp

ans = sum(dp[g][g] for g in range(1, m+1)) % MOD

（弹幕：就这？new 一个二维数组就把三维降了？） （弹幕：我还没反应过来，他就已经把内存砍了） （弹幕：DP 界的节能标兵，环保大使）

老白解说：来，镜头切过来，咱们看看二号选手到底省在哪了。

回想下一号的代码，聪明的你一定发现了——dp[i+1] 只依赖 dp[i] ！前面的 dp[0]、dp[1]……一直到 dp[i-1]，算完之后就再也没人翻过牌子。那还留着它们干嘛？占着内存不干活，纯纯的电子僵尸。

二号选手就直接把三维数组的最外层维度给砍了，打法极其清爽：只留一张当前层表 dp，每处理一个新数，就拿一张全新的空白表 new_dp，根据 dp 里的状态往上面填新状态。等这一轮全部算完，把 new_dp 赋值给 dp，旧表原地去世，自动等垃圾回收。

空间直接从 O(n·m²) 断崖式跌到 O(m²)——也就是 200×200 = 4 万个格子。这招在圈里叫滚动数组优化，说白了就是把不用的历史页面统统撕掉，只留当前这一页在手上转。

不过有个细节千万别漏：他没有原地更新。因为同一个旧状态要同时“广播”给到三个新状态，如果直接在原表上改，第一个新状态写进去就把旧数据污染了，后面读到的全是脏数据，方案数直接乱成一锅粥。所以 new_dp 这张暂存表是必须的——等所有广播全部发完，再整体切换指针，干净利落。经常玩 3A 大作的观众看到这儿应该会心一笑：这不就是经典的双缓冲嘛，渲染一帧、显示一帧，谁也别干扰谁。

AC 图标，第二次亮起！

（弹幕：双缓冲，爷青回，打游戏的老懂哥了） （弹幕：从 O(n·m²) 到 O(m²)，内存直接缩了 200 倍，狠人） （弹幕：老实人 + 节能侠，一个稳一个省，这对 CP 我磕了）

三号选手·“回头是岸”递归 DFS

“你们这些迭代的，都是计算器，让我来教教你们什么是逆向思维。”三号选手潇洒地甩出一段递归式。

@cache
def dfs(i, j, k):
    if i < 0:
        # 没有待处理的数了，(j,k) 就是最终状态。相等算1，不等算0
        return 1 if j == k else 0
    return (dfs(i - 1, j, k)                        # 不选
            + dfs(i - 1, gcd(j, nums[i]), k)        # 放 seq1
            + dfs(i - 1, j, gcd(k, nums[i]))) % MOD # 放 seq2

return (dfs(len(nums) - 1, 0, 0) - 1) % MOD

（弹幕：这递归看着像倒放，脑子倒着转好难） （弹幕：i < 0 返回 1 如果 j==k，那空序列也算？） （弹幕：最后减一是把两个都空的方案扣掉，绝了）

老白解说：别被索引绕晕，三号这套递归其实就一个画面——

想象你把数组 nums 一字排开，面前站着第 i 个宝箱。这个宝箱右边的所有箱子，已经全部开完、分好队伍了，此时两队 gcd 分别是 j 和 k。左边包括当前这个在内的 i 个箱子，还完全没动。

dfs(i, j, k) 就是在问：站在当前这个箱子(i)上，往左一路开到第一个箱子(0)，把剩下的全部分配完以后，最终能让两边 gcd 相等的方案数有多少。

所以每次递归 i-1，相当于指针往左挪一格，又多搞定了一个箱子。等到 i < 0，说明连最左边那个也分完了，整个数组瓜分结束，此时的 (j,k) 就是终局。相等就计 1，不等就计 0。

这里有一个小细节：终局判定里，j=k=0 也是相等，所以全空方案会被算进来。最后答案减 1，就是为了把这个“两人全程挂机”的摸鱼局面踢出去。

转移的时候，当前宝箱 nums[i] 三选一，每条路的未来方案数直接加起来就完事。为什么不用 +=？因为每个状态要的未来，就是它三个子状态未来的总和，子状态的结果干干净净地 return 回来，一把加走，这就是递归天然的拉取优势，子问题的结果直接拿来用。

最后加上 @cache，每个 (i,j,k) 只算一次。状态总数和正向 DP 一模一样，但代码却像数学公式一样简洁。这就叫——从终点往回看，反而把路看得更清楚。

时间 O(n·m²)，空间 O(n·m²)（缓存的锅）。AC 图标第三次亮起！

（弹幕：懂了，正向 DP 是“我走过去”，递归是“我从终点倒回来”） （弹幕：这不就是游戏里从终点往起点标最短路径嘛） （弹幕：@cache 是真的香，一行代码省掉手写 DP 表）

四号选手·“反转未来”期望 DP

一道人影急不可耐地冲了出来：“三号递归是自上而下，让我把它翻成自底向上的迭代版，让你们看看什么叫双向奔赴。”

n = len(nums)
m = max(nums)

# dp[i][j][k]：还有 i 个宝箱没开，当前 gcd=(j,k)，未来能赢的方案数
dp = [[[0] * (m+1) for _ in range(m+1)] for _ in range(n+1)]

# 终点：0 个宝箱没开，(j,k) 就是终局。相等且非空算赢
for g in range(1, m+1):
    dp[0][g][g] = 1   

for i, num in enumerate(nums):
    for j in range(m+1):
        for k in range(m+1):
            dp[i+1][j][k] = (dp[i][j][k]                    # 不选 num
                           + dp[i][gcd(j, num)][k]          # num 进 seq1
                           + dp[i][j][gcd(k, num)]) % MOD   # num 进 seq2
return dp[n][0][0]

（弹幕：转移直接用 = 不用 +=？这哥们跟一号有仇是吧） （弹幕：dp[n][0][0] 就是答案？不用减一也不用求和？我人傻了） （弹幕：这个叫期望 DP 吗？我看是“反直觉 DP”）

老白解说：四号这套叫未来期望 DP，是三号递归的迭代翻译版。和一号正向 DP 放一块看，绝对能让你直呼“原来 DP 还能双向奔赴”。

先把一号拉回来当参照物：一号正向 DP 的 dp[i] 存的是“已经处理了前 i 个，总共攒了多少方案”。他是站在过去，把当前状态推送给未来——一个目标格子被好几个源头同时投喂，所以必须 +=。

四号呢？完全反过来。他的 dp[i] 里，i 不是“已经处理了多少”，而是**“还剩多少没处理”**。你可以想象一条从 0 到 n 的进度条：

  • dp[0] 在数轴最左端，代表还剩 0 个宝箱——全部开完了，没得选了。此时的 (j,k) 就是最终成绩单。如果两队 gcd 相等且都不为空（g≥1），那就是一种合法结局，dp[0][g][g]=1。至于 dp[0][0][0]？两人全程摸鱼，违反“非空”规定，直接判 0。正向 DP 最后才扣掉的空序列，他在边界就提前毙了。
  • dp[n] 在数轴最右端，代表还剩 n 个宝箱——一个都还没碰。dp[n][0][0] 问的就是：从起点（两队空空）出发，一路开到终点，最终能赢的方案数。这不就是原题答案本尊？所以最后直接返回，一步到位，不用像递归那样手动减一，也不用像正向 DP 那样加和。

转移的时候，四号用的是拉取。dp[i+1][j][k] 表示还剩 i+1 个宝箱没开，状态是 (j,k)，它朝前迈一步（往 i 的方向），多开了一个宝箱 num。这个 num 去哪了？三种可能，对应三个“更靠近终点”的未来档案：

  • 跳过了 → 未来路数就是 dp[i][j][k]
  • 进了 A 队 → 未来路数就是 dp[i][gcd(j,num)][k]
  • 进了 B 队 → 未来路数就是 dp[i][j][gcd(k,num)]

三份档案拉过来一加，直接赋值。所以，为什么不用 +=？因为一个目标格子的三个来源唯一且确定，没有第四个人能插队。这跟正向 DP 一个目标被一堆源头狂轰正好相反。

也就是说，一号正向 DP 是“站在过去，推给未来，用 += 收包裹”；四号期望 DP 是“站在未来，往过去拉绳子，用 = 一把拽回”。同一个状态图，正着跑和倒着跑，踩的格子一样多，但姿势完全不同——像极了你打游戏时，有人喜欢从老家往外推塔，有人喜欢从终点往回标最短路径。两种画风，一个答案，都能通关。

时间 O(n·m²)，空间 O(n·m²)（同样可滚动优化）。AC 图标第四次亮起！

（弹幕：懂了，dp[i] 里的 i 是“离终点还有几步”，不是“已经走了几步”） （弹幕：推送 vs 拉取，DP 界的 PUSH 和 PULL，像 Git 一样） （弹幕：正向 DP 是从过去推未来，这个是从未来拉过去，双向奔赴！） （弹幕：我 CPU 烧了但我大受震撼）

温馨提示：看到这里，如果你的CPU 还没有冒烟、也没有被前面四位绕晕——老白先给你竖个大拇指！

但别高兴太早，因为接下来登场的神秘嘉宾，将用一行公式，把你刚刚建立起来的算法世界观，原地干碎！

（全场灯光暗了下来，一束追光打在入口处，BGM切成了管风琴版的《哥德巴赫猜想变奏曲》）

五号神秘嘉宾·“数论降维”倍数容斥

一位穿着数论斗篷的选手踱步而出——他径直走到黑板前，抬手写了一个希腊字母——μ（mu）。

（弹幕：？？？？？这人谁？？） （弹幕：μ？那不是莫比乌斯函数吗，数论大佬的身份证） （弹幕：莫比乌斯是谁？我只认识莫比乌斯环）

“前面四个，都是好样的。”斗篷人的声音不高，却像混响拉满了一样在现场回荡，“可你们终究是在状态图里一步一步爬。而我——要直接把整张图烧成了灰。”

他转过身，在黑板上龙飞凤舞，先甩出了一套预处理：

MOD = 1_000_000_007
MX = 201

# lcms[g1][g2] 提前算好最小公倍数，后面查表秒出
lcms = [[lcm(i, j) for j in range(MX)] for i in range(MX)]

# pow2[i] = 2^i，pow3[i] = 3^i，顺手预处理好，后面省时间
pow2 = [1] * MX
pow3 = [1] * MX
for i in range(1, MX):
    pow2[i] = pow2[i - 1] * 2 % MOD
    pow3[i] = pow3[i - 1] * 3 % MOD

# 莫比乌斯函数 μ，用筛法一口气全算完
mu = [0] * MX
mu[1] = 1
for i in range(1, MX):
    for j in range(i * 2, MX, i):
        mu[j] -= mu[i]

（弹幕：一上来就是 lcm 表、幂次表、莫比乌斯筛，这排场！） （弹幕：原来他不写循环不是不写，是写在预处理里了） （弹幕：每个字我都认识，连起来像在看天书） （弹幕：这就是数学系大佬的平 A 吗，太痛了）

接着，是主函数部分——他先搭出整个解法最核心的脚手架：统计每种 gcd 候选值能管到多少个元素。

def subsequencePairCount(nums: List[int]) -> int:
	# cnt[i] 表示 nums 中能被 i 整除的元素个数
    cnt = [0] * (m + 1)
    for x in nums:
        cnt[x] += 1
    # 筛法倒灌：cnt[i] 把 i 的所有倍数的计数也吸收进来
    for i in range(1, m + 1):
        for j in range(i * 2, m + 1, i):
            cnt[i] += cnt[j]

（弹幕：cnt[i] 本来只记 i 自己，现在把 2i、3i 全卷进来了） （弹幕：这不就是埃筛那套吗，换皮不换芯） （弹幕：懂了，cnt[i] 就是“元素里有多少个 i 的信徒”）

脚手架搭好，他继续在黑板上写下整个解法最吓人、也最漂亮的部分！

    f = [[0] * (m + 1) for _ in range(m + 1)]
    for g1 in range(1, m + 1):
        for g2 in range(1, m + 1):
            l = lcms[g1][g2]              # 同时是 g1 和 g2 倍数的条件 = lcm 的倍数
            c  = cnt[l] if l <= m else 0  # 两个队的“公共兵源”
            c1 = cnt[g1]                  # 只效忠 seq1 的兵源
            c2 = cnt[g2]                  # 只效忠 seq2 的兵源
            f[g1][g2] = (pow3[c] * pow2[c1 + c2 - c * 2]
                         - pow2[c1] - pow2[c2] + 1) % MOD
            
    ans = 0
    for i in range(1, m + 1):
        for j in range(1, m // i + 1):
            for k in range(1, m // i + 1):
                ans = (ans + mu[j] * mu[k] * f[j * i][k * i]) % MOD
	return ans

（弹幕：来了来了，那个传说中的组合公式！） （弹幕：3^c × 2^{c1+c2-2c} 是啥？幂指数比我吃过的盐还多） （弹幕：这哪是写代码，这是在用排列组合直接心算子序列对数）

老白解说：各位屏幕前还没被抬走的朋友！恭喜你们，接下来是整个 EP03 的智商巅峰时刻！你们可能已经被这坨指数砸晕了，但别怕，我用人话给你们拆。

前面四位，不管正着走还是倒着走，本质上都是在状态图 (i, j, k) 里一步步爬——每个元素都要决定去留，每个 gcd 都要实时更新。但五号大手一挥：我不追踪过程，我直接锁定终局——最终两个序列的 GCD 都等于某个 g 有多少种可能！

定义 f[g1][g2] 表示seq1 的gcd 是 g1 的倍数、seq2 的 gcd 是 g2 的倍数的方案数。所有元素按“倍数身份”分成三个帮派：

  • 帮派 C：同时是 g1 和 g2 的倍数（也就是 lcm(g1,g2) 的倍数）。这些元素两头通吃，能进 seq1、能进 seq2、也能谁都不跟。每个元素 3 种选择，一共有 c 个，所以贡献 3^c。
  • 帮派 A：只是 g1 的倍数，但不是 g2 的倍数。这些兵只能给 seq1 用，或者不选。每个元素 2 种选择，数量是 c1 - c，贡献 2^{c1-c}。
  • 帮派 B：只是 g2 的倍数，但不是 g1 的倍数。同理，只能进 seq2 或者不选，数量 c2 - c，贡献 2^{c2-c}。

三个帮派的方案数乘起来：3^c × 2^{c1-c} × 2^{c2-c}，化简就是 3^c × 2^{c1+c2-2c}。

但这算出来的是“两个序列的 gcd 分别是 g1 和 g2 的倍数”的全部方案，里面混着 seq1 为空、seq2 为空的非法情况。所以要扣掉 seq1 空掉的情况（2^{c2}），扣掉 seq2 空掉的情况（2^{c1}），再把“两个都空”多扣的一次加回来（+1）。整个公式f[g1][g2] = 3^c * 2^{c1+c2-2c} - 2^{c1} - 2^{c2} + 1 就是这么来的——小学的“总数减不合法”，被指数一包装，直接变成了一道排列组合奥数题。

（弹幕：好家伙，原来每个指数都在数“二选一”还是“三选一”） （弹幕：这不就是“先算总数，再扣不合法”的初中数学，但套上了 gcd 的壳） （弹幕：f[g1] [g2] 存的就是“gcd 是 g1 和 g2 倍数的非空方案数”，懂了！）

老白继续：好了，f 表填完了，但里面装的是“倍数方案”，不是我们想要的“恰好相等”。得请出今天的终极大杀器——莫比乌斯反演。

再看下精彩回放：

ans = 0
for i in range(1, m + 1):
    for j in range(1, m // i + 1):
        for k in range(1, m // i + 1):
            ans = (ans + mu[j] * mu[k] * f[j * i][k * i]) % MOD
return ans

（弹幕：三重循环？但 j 只到 m//i，实际跑不了多少次） （弹幕：莫比乌斯函数：我是一把筛子，专筛倍数，精准到微克） （弹幕：mu[j]*mu[k] 就是容斥的开关，把倍数层层剥掉） （弹幕：f 表里混着 (g1,2g1,3g1…) 的方案，μ 全给筛干净了）

老白继续：到这里还能挺住的朋友，你们是真正的勇士！

这最后一步的逻辑，说白了就是：f[g1][g2] 装着所有 (g1的倍数, g2的倍数) 的方案。现在我只想要恰好等于 g 的方案。怎么筛？莫比乌斯函数 μ 自带正负号，按倍数关系一乘一累加，多余的倍数层自动抵消，剩下的就是恰好那层。这就像用一张精密筛网，把所有粗颗粒滤掉，只留你想要的那一粒金沙。

整个过程，没有 dp 数组，没有 for num in nums 的主循环，甚至看不到“子序列”三个字。因为五号选手用组合数学，把子序列选择的排列组合一口吞进了指数里；又用莫比乌斯反演，把容斥的脏活累活全自动化了。复杂度？时间 O(m² log m) 级别，m=200 的时候比前面几位还快；空间 O(m²)，几张表就搞定。

AC 图标，第五次亮起——全环形竞技场上炸出金色烟花，飘下一串串数学符号——弹幕池瞬间被同一个符号刷屏：

（弹幕：μ μ μ μ μ） （弹幕：μ门永存） （弹幕：今天不是算法竞技场，是《走近科学》数论特辑） （弹幕：看完我大受震撼，感觉自己学了算法，又好像学了数学，又好像啥也没学） （弹幕：老白，下一期能不能来点阳间题，我的脑细胞阵亡了百分之九十）

伤害统计 & 赛后锐评

老白擦汗：看到这里，如果你还没有退出直播间——你是条汉子！今天的 EP03，咱们从正向 DP 的步步为营，一路杀到莫比乌斯反演的公式碾压。能跟到最后的，都是算法界的散仙！

导播，切数据面板！

选手流派核心操作时间复杂度空间复杂度骚气指数推荐场景结果
一号历史累积 DP正向推送，老实 += 记账O(n·m²)O(n·m²)⭐⭐面试求生✅AC
二号滚动数组空间压缩，双缓冲轮换O(n·m²)O(m²)⭐⭐⭐内存敏感✅AC
三号递归 DFS倒着问路，@cache 兜底O(n·m²)O(n·m²)⭐⭐⭐⭐快速原型✅AC
四号期望 DP反向拉取，= 一把梭O(n·m²)O(n·m²)⭐⭐⭐⭐对称思维练习✅AC
五号倍数容斥莫比乌斯反演，公式碾压O(m² log m)O(m²)⭐⭐⭐⭐⭐数学系炸鱼✅AC

（弹幕：最稳妥的还是正向 DP，不容易错） （弹幕：不仅公式帅，速度还快，五号真的是人吗） （弹幕：空间从三维砍到二维，时间从八百万次砍到几十万次！） （弹幕：O(m² log m) 在 m=200 的时候就跑几十万次，比八百万次快了不止一个量级） （弹幕：全场最佳：莫比乌斯，输出全靠公式）

老白的出装推荐——请选择你的英雄：

  • 面试求生：选一号历史累积 DP。逻辑直白，边界清晰，面试官一秒看懂你在干嘛。写出来就是“我基本功扎实”的无声宣言。稳，才是面试的第一生产力。
  • 面试官追问“能优化吗”：掏出二号滚动数组。把 O(n·m²) 的空间一刀砍成 O(m²)，面试官当场在心里给你加分。“这个候选人，有工程意识。”
  • 想秀递归思维：亮三号递归 DFS。代码短，@cache 一行封神，Python 玩家看了直呼内行。但记得搞清楚“从终点往回问”的状态定义，否则面试官会以为你在背题。
  • 理解 DP 本质：把四号期望 DP 写出来。一旦你同时掌握了“推送”和“拉取”两种转移姿势，DP 在你眼里就不再是玄学，而是双向奔赴的对称艺术。
  • 周赛装逼 / 数论专精：掏出五号倍数容斥。代码短、跑得快、数学味儿冲破天际，队友会以为你开了天眼。

（弹幕：这题 M=200 所以我选 DP，要是 M=1e5 我就跪着抄容斥） （弹幕：我选第六种：CV 大法，复制粘贴一把梭） （弹幕：一号和二号最实用，三号和四号最好玩，五号最吓人） （弹幕：今天不是算法竞技场，是《算法博物馆》开馆日）

尾声：

好了，今天的「算法竞技场 EP03」到此全部打板收工！这题的五个解法，就像 RPG 里的五种职业，各有神通。觉得这期让你对 DP 和容斥有了新的理解，把 “我全都要” 打在公屏上！Bug 清零，Offer 拿到手软，GCD 永远等于你期望的那个数。我是老白，在 EP04 的副本门口蹲你，咱们下期见！

知识共享许可协议
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。