更新题目 l/r 子序列走到 y 的方案数

题目 visa-lr-subsequence-moves · 修改（rev 13） · cc · 2026-10-27 00:33
body

@@ -1,8 +1,30 @@
+## TL;DR
+
+- 题目按不同的字符串去重，例子是 7，按下标组合数会得到 20，见「题目」。
+- 以 c 结尾的不同子序列，等于当前所有不同子序列（含空串）各接一个 c，所以新算出的一行整个覆盖旧的 `dp[c]`，见「思路」。
+- 把旧值加上去的写法数的就是下标组合数，`"rr"` 这个小例子就能看出来，见「小例子：为什么要覆盖」。
+- 合法走法离 `x`、离 `y` 都不超过 $|s|$ 格，数组只开这个窗口，时间降到 $O(|s| \cdot \min(n, |s|))$，见「只看走得到的位置」。
+- 越界要在每一步检查，`"lr"`、n = 2、x = 0、y = 0 这组输入能查出只看终点的错，见「易错点」。
+- 不按结尾字符分开的 `T` 加 `last[c]` 写法只是换了形式，存的还是那两行，见「能不能不按结尾分开」。
+- 改成按下标组合数，只要把覆盖换成相加，见「Follow-up」。
+
 ## 题目
 
-数轴上的位置是 0 到 n。给一个只含 `'l'` 和 `'r'` 的字符串 `s`、起点 `x`、终点 `y`。从左到右处理 `s` 的每个字符，每个字符可以跳过，也可以用一次：`'l'` 往左走一格，`'r'` 往右走一格，每走一步都不能出 [0, n]，中途有一步出界的子序列不算。每一种不同的选法（也就是 `s` 的一个不同的子序列）对应一条走法。问有多少个**非空**子序列能让你从 `x` 正好停在 `y`，答案对 10^9 + 7 取模。
+数轴上的位置是 0 到 n。给一个只含 `'l'` 和 `'r'` 的字符串 `s`、起点 `x`、终点 `y`。从左到右处理 `s` 的每个字符，每个字符可以跳过，也可以用一次：`'l'` 往左走一格，`'r'` 往右走一格，每走一步都不能出 $[0, n]$，中途有一步出界的子序列不算。每一种不同的选法（也就是 `s` 的一个不同的子序列）对应一条走法。问有多少个**非空**子序列能让你从 `x` 正好停在 `y`，答案对 $10^9 + 7$ 取模。
+
+「不同」按选出来的字符串算：两组不同的下标拼出同一个字符串，只算一次。
 
 例子：`s = "rrlrlr"`，`n = 6`，`x = 1`，`y = 2`，答案 7。
 
+这 7 个字符串是 `r`、`lrr`、`rlr`、`rrl`、`rlrlr`、`rrllr`、`rrlrl`。除了 `r` 本身，其余 6 个都是在 `r` 之外多走了一对或两对互相抵消的 `l` 和 `r`，最后净右移一格。按下标组合数时，光是 `r` 就要算 4 次（4 个 `'r'` 任选一个），20 就是这样多出来的。
+
+还有几处边界题面没写死，「代码」一节的窗口版这样处理：
+
+- `x == y` 时，空串（一步不走）不算，因为题目要非空。像 `"rl"` 这样走出去又绕回来的算。
+- `n == 0` 时一步都走不了，答案是 0。
+- `x` 或 `y` 不在 $[0, n]$ 里，返回 0。
+
+原帖里 $|s|$ 和 n 的范围、时限都未核实。
+
 ## 面经里怎么考的
 
@@ -11,7 +33,18 @@
 关键在「不同」：例子的答案 7 是按**不同的字符串**数出来的。如果按下标组合数（同一个字符串由不同下标选出来算多次），同一个例子会得到 20。题面读到「distinct subsequence」就要往 LC 940 的去重写法上靠。
 
+动手前先拿例子手算一下是 7 还是 20，确认题意再写。
+
 ## 思路
 
+给定一个由 `'l'`、`'r'` 组成的字符串，从 `x` 出发怎么走是确定的，每一步停在哪也是确定的。所以「数不同的子序列」和「数不同的走法」是一回事。
+
 LC 940 的去重办法是：只记「以字符 c 结尾的不同子序列有多少个」。处理到一个新的字符 c 时，以 c 结尾的不同子序列，正好等于「当前所有不同子序列（包括空串）后面各接一个 c」，这些新串互不相同，而且已经包含了以前所有以 c 结尾的串，所以直接**覆盖**旧的计数，而不是累加，这样就不会重复。
+
+「正好等于」可以从两个方向验证。设处理的是第 i 个字符，它是 c：
+
+- 前 $i - 1$ 个字符的每个不同子序列 `t`，接上 c 得到的 `t + c` 都能从前 i 个字符里选出来：`t` 从前 $i - 1$ 个字符里选，最后的 c 用第 i 个字符。
+- 反过来，任何一个以 c 结尾、能从前 i 个字符里选出来的串 `t + c`，把它最后的 c 对到它在 `s` 里匹配的位置 j（$j \le i$），前缀 `t` 就是从前 $j - 1$ 个字符里选出来的，所以 `t` 也是前 $i - 1$ 个字符的子序列。
+
+不同的 `t` 接上 c 还是不同的串，所以这个集合里没有重复。
 
 这题在此基础上多了一个维度：位置。先把完整的状态写出来，它有三维：
@@ -21,8 +54,8 @@
 - `p`：从 `x` 出发按这个子序列走完，停在哪个位置。
 
-`dp[i][c][p]` 表示：在 `s` 前 i 个字符能选出的所有不同子序列里，以 c 结尾、走完停在 p 的有几个。i = 0 时还没有非空子序列，所有格子都是 0。处理第 i 个字符时（i 从 1 数起，这个字符是 `ch = s[i-1]`），由第 i−1 层算出第 i 层，分两步：
+`dp[i][c][p]` 表示：在 `s` 前 i 个字符能选出的所有不同子序列里，以 c 结尾、走完停在 p 的有几个。$i = 0$ 时还没有非空子序列，所有格子都是 0。处理第 i 个字符时（i 从 1 数起，这个字符是 `ch = s[i-1]`），由第 $i-1$ 层算出第 i 层，分两步：
 
 1. 重算以 `ch` 结尾的计数，也就是 `dp[i][ch][p]`，p 取 0 到 n 的每一个位置。分两小步：
-   1. 先算「前 i−1 个字符的所有不同子序列停在 p 的个数」`all[i-1][p] = (p == x ? 1 : 0) + dp[i-1]['l'][p] + dp[i-1]['r'][p]`，那个 1 是空串（还停在起点）。
+   1. 先算「前 $i-1$ 个字符的所有不同子序列停在 p 的个数」`all[i-1][p] = (p == x ? 1 : 0) + dp[i-1]['l'][p] + dp[i-1]['r'][p]`，那个 1 是空串（还停在起点）。
    2. 把 `all[i-1]` 往 `ch` 的方向挪一格，得到 `dp[i][ch][q] = all[i-1][p]`，其中 q 是 p 挪一格后的位置，越界的丢掉。新算出的 `dp[i][ch][·]` 只由 `all[i-1]` 决定，和 `dp[i-1][ch]` 原来的值无关，这就是上面说的「覆盖」。
 2. 结尾字符不是 `ch` 的计数原样继承：对每个位置 p，`dp[i][c'][p] = dp[i-1][c'][p]`（`c' ≠ ch`）。原因是用到 `s[i-1]` 的子序列，`s[i-1]` 一定是最后一个字符，这样的子序列都以 `ch` 结尾，所以以 c' 结尾的不同子序列和处理 `s[i-1]` 之前完全一样。
@@ -30,9 +63,38 @@
 最后答案是 `dp[|s|]['l'][y] + dp[|s|]['r'][y]`，空串不在里面，正好满足「非空」。
 
+> [!say] Because the question counts distinct subsequences, I track, for each ending character and each position, how many distinct subsequences end there. When I see a character c, every distinct subsequence so far extended by c gives exactly the new set ending in c, so I overwrite that row instead of adding to it.
+
 ### 压缩掉 i 这一维
 
-第 i 层只用到第 i−1 层，所以只留一层 `dp[c][p]`，每处理一个字符就把它更新成下一层。滚动以后，第 2 步的「原样继承」什么都不用做，剩下的就是第 1 步：算出 `all_`，往 `ch` 的方向挪一格，覆盖 `dp[ch]`。空间从三维表的 O(|s| · n) 降到 O(n)。
-
-在算 `all_` 时读到的全是上一层的值的前提下，压缩以后结果不变。下面的代码先用旧的 `dp` 把 `all_` 整个算完，再把挪格的结果写进新数组 `new`，最后才赋给 `dp[ch]`，所以满足这个前提。如果 `all_` 还没算完就往 `dp[ch]` 里写，`all_` 就会读到这一层刚写进去的值，等于把第 i 层和第 i−1 层混在一起用了。
+第 i 层只用到第 $i-1$ 层，所以只留一层 `dp[c][p]`，每处理一个字符就把它更新成下一层。滚动以后，第 2 步的「原样继承」什么都不用做，剩下的就是第 1 步：算出 `all_`，往 `ch` 的方向挪一格，覆盖 `dp[ch]`。空间从三维表的 $O(|s| \cdot n)$ 降到 $O(n)$。
+
+在算 `all_` 时读到的全是上一层的值的前提下，压缩以后结果不变。下面的代码先用旧的 `dp` 把 `all_` 整个算完，再把挪格的结果写进新数组 `new`，最后才赋给 `dp[ch]`，所以满足这个前提。如果 `all_` 还没算完就往 `dp[ch]` 里写，`all_` 就会读到这一层刚写进去的值，等于把第 i 层和第 $i-1$ 层混在一起用了。
+
+### 小例子：为什么要覆盖
+
+`s = "rr"`，`n = 2`，`x = 0`。数组下标是位置 0、1、2。
+
+| 步骤 | `all_`（含空串） | 覆盖后的 `dp["r"]` | 把旧值加上去的 `dp["r"]` |
+| --- | --- | --- | --- |
+| 第 1 个 `'r'` | [1, 0, 0] | [0, 1, 0]，是串 `r` | [0, 1, 0] |
+| 第 2 个 `'r'` | [1, 1, 0]，空串在 0，`r` 在 1 | [0, 1, 1]，是 `r` 和 `rr` | [0, 2, 1] |
+
+第 2 步挪出来的新数组里，位置 1 上的 1 就是 `r`（空串接一个 `r`），已经包含了第 1 步的那个 `r`。再把旧值加上去，位置 1 变成 2，`r` 被数了两次，这正是用第 1 个和第 2 个 `'r'` 各选一次的两种下标选法。
+
+所以「把旧值加上去」的写法数的就是下标组合数，一般情况的推导见 Follow-up「如果要按下标组合数呢」。「测试用例」一节里随机对拍，加上去的写法和按下标暴力数的结果每组都一样。
+
+### 只看走得到的位置
+
+数组开到 $n + 1$ 格，时间是 $O(|s| \cdot n)$。n 比 $|s|$ 大很多时，绝大多数格子一直是 0，白白参与计算，$|s| = 2000$、$n = 10^5$ 时逐格版比窗口版慢 40 多倍（实测见「复杂度」）。
+
+一个合法的串长度 L 不超过 $|s|$，它从 `x` 出发、停在 `y`，途中经过的任何位置 p 离 `x` 不超过 L 步，离 `y` 也不超过 L 步（从 p 还要走回 `y`）。所以合法的串一直待在下面这个窗口里：
+
+$$
+[\max(0,\ x - |s|,\ y - |s|),\ \min(n,\ x + |s|,\ y + |s|)]
+$$
+
+数组只开这个窗口那么宽，下标减去窗口左端 `lo`。挪格时被挪出窗口的串分两种。窗口的边是 0 或 n 时，挪出去的串真的出界了，本来就不算。窗口的边是 $y - |s|$ 或 $y + |s|$ 时，挪出去的串离 `y` 已经超过 $|s|$ 步，而它和它以后接出来的串都不长于 $|s|$，走不回 `y`。（离 `x` 超过 $|s|$ 步的情况不会出现，长度不超过 $|s|$ 的串走不了那么远。）这些串和它们的后续都不会计入答案，所以丢掉不影响结果。窗口宽度不超过 $2|s| + 1$，时间变成 $O(|s| \cdot \min(n, |s|))$。另外 $|x - y| > |s|$ 时根本走不到，直接返回 0，这也保证了 `x` 和 `y` 都在窗口里。
+
+> [!say] A valid walk never gets farther than len(s) steps from x or from y, so I only keep the positions inside that window. That makes the run time O(len(s) times min(n, len(s))) no matter how large n is.
 
 ## 代码
@@ -56,9 +118,73 @@
 ```
 
-本机跑过题面的例子（输出 7），并在 2000 组随机小数据（|s| ≤ 10，n ≤ 4）上和暴力枚举去重的结果对拍，全部一致。
+本机跑过题面的例子（输出 7），并在 2000 组随机小数据（$|s| \le 10$，$n \le 4$）上和暴力枚举去重的结果对拍，全部一致。
+
+下面称上面这段为逐格版。窗口版按「只看走得到的位置」只开窗口那么宽，算法和逐格版相同：
+
+```python
+MOD = 10**9 + 7
+
+
+def reachable_window(n, x, y, steps):
+    """Positions a valid walk of at most `steps` moves can visit: within `steps` of x and of y, inside [0, n]."""
+    return max(0, x - steps, y - steps), min(n, x + steps, y + steps)
+
+
+def shift_one_step(counts, move):
+    """Move every count one cell left ('l') or right ('r'); counts pushed off either end are dropped."""
+    if move == "r":
+        return [0] + counts[:-1]
+    return counts[1:] + [0]
+
+
+def count_distinct_subsequence_walks(s, n, x, y):
+    if not (0 <= x <= n and 0 <= y <= n) or abs(x - y) > len(s):
+        return 0
+    lo, hi = reachable_window(n, x, y, len(s))
+    width = hi - lo + 1
+    # ends_with[c][i]: distinct non-empty subsequences ending in c that stop at position lo + i
+    ends_with = {"l": [0] * width, "r": [0] * width}
+    # counts[i]: all distinct subsequences so far, the empty one included, that stop at lo + i
+    counts = [0] * width
+    counts[x - lo] = 1
+    for move in s:
+        if move not in ends_with:
+            raise ValueError(f"unexpected character {move!r}")
+        new_row = shift_one_step(counts, move)
+        old_row = ends_with[move]
+        counts = [(total - old + new) % MOD for total, old, new in zip(counts, old_row, new_row)]
+        ends_with[move] = new_row  # overwrite, never add
+    return (ends_with["l"][y - lo] + ends_with["r"][y - lo]) % MOD
+```
+
+窗口版里的 `ends_with` 就是逐格版的 `dp`，`counts` 就是 `all_`。两版的差别有这几处：
+
+- **数组宽度**：逐格版开 $n + 1$ 格，窗口版开 `reachable_window` 算出的宽度，不超过 $\min(n + 1, 2|s| + 1)$。
+- **范围检查**：窗口版开头先检查 `x`、`y` 是否在 $[0, n]$ 里、$|x - y|$ 是否超过 $|s|$，不满足就返回 0。逐格版默认题面保证 `x`、`y` 在范围内。
+- **挪格**：逐格版逐格写 `if 0 <= q <= n`。窗口版用切片，`'r'` 时在左边补一个 0、去掉最右一格（停在窗口右端的串再往右就出了窗口），`'l'` 时去掉最左一格、在右边补 0。数组长度始终是窗口宽度，出窗口的状态自然被丢掉。切片在 C 里做，比逐格写 Python 循环快。
+- **`counts` 的更新**：逐格版每个字符都从两行重新加出 `all_`。窗口版里两行中只有 `ends_with[move]` 变了，所以 `counts` 减去旧的那一行、加上新的那一行就行。
+
+`n == 0` 时窗口只有一格，挪完就是 `[0]`，答案是 0。两版在 2026-10-27 云端（Python 3.13）重跑的结果见「测试用例」：题面例子都是 7，随机对拍全部和暴力一致。
 
 ## 复杂度
 
-时间 O(|s| · n)，空间 O(n)。
+时间 $O(|s| \cdot n)$，空间 $O(n)$。
+
+窗口版时间 $O(|s| \cdot \min(n, |s|))$：每个字符挪一次格、更新一次 `counts`，都是窗口宽度那么多次操作。空间 $O(\min(n, |s|))$，存三行。
+
+2026-10-27 在云端 Python 3.13 上实测（随机 `s`，种子 20261027，`x`、`y` 都取 n // 2，每组跑一次）：
+
+| `s` 的长度 | n | 逐格版 | 窗口版 |
+| --- | --- | --- | --- |
+| 2000 | 2000 | 1.08 秒 | 0.42 秒 |
+| 2000 | $10^5$ | 36.08 秒 | 0.75 秒 |
+| 2000 | $10^9$ | 没跑（要开 $10^9$ 格的数组） | 0.72 秒 |
+| 5000 | 5000 | 7.10 秒 | 2.71 秒 |
+| $10^4$ | 1000 | 3.71 秒 | 1.38 秒 |
+| $10^4$ | $10^4$ | 30.84 秒 | 11.70 秒 |
+
+每一行两版的答案相同。这几组 `x`、`y` 都在正中间，n 不超过 $2|s|$ 时窗口就是整个 $[0, n]$，并不比 $n + 1$ 格窄，窗口版快的那两三倍来自切片挪格和增量更新 `counts`。为了分开这两个因素，把窗口版的 `reachable_window` 换成直接返回 `(0, n)`、其余不变再跑：$|s| = 2000$、$n = 10^5$ 要 19.03 秒，$|s| = n = 2000$ 是 0.41 秒，和窗口版几乎一样。
+
+$|s| \cdot \min(n, |s|)$ 是 $2.5 \times 10^7$ 时窗口版要 2.71 秒，到 $10^8$ 要 11.70 秒。HackerRank 的时限未核实。$|s|$ 和 n 都到 $10^5$ 的话，任何语言的 $O(|s| \cdot \min(n, |s|))$ 都要算 $10^{10}$ 次，题目不会这样出，所以实际数据范围应该在上面这张表的量级【推断】。还要更快的话，见 Follow-up 里的 numpy 写法。
 
 ## 易错点
@@ -66,13 +192,89 @@
 - 按下标组合去数会得到 20，不是 7。
 - 覆盖 `dp[c]` 而不是加上去，这是去重的关键。照「选或不选」写成「旧值 + 取当前」会把同一个字符串数多次，反例见[「转移方程按结尾字符分两种情况」](#转移方程按结尾字符分两种情况)。
-- 「走完不能出界」是每一步都要检查，不是只看终点；上面的写法在每次挪格时丢掉越界的状态。合法走法的每个前缀也合法，所以「以 c 结尾的不同合法子序列 = 每个不同合法子序列后面接一个 c，再去掉出界的」仍然成立，覆盖的写法不受边界影响。
+- 「走完不能出界」是每一步都要检查，不是只看终点。上面的写法在每次挪格时丢掉越界的状态。合法走法的每个前缀也合法，所以「以 c 结尾的不同合法子序列 = 每个不同合法子序列后面接一个 c，再去掉出界的」仍然成立，覆盖的写法不受边界影响。
+- 只看终点的反例：`s = "lr"`、n = 2、x = 0、y = 0，串 `lr` 第一步就走到 −1，正确答案 0，只看终点的写法得 1，题面的例子查不出这个错。边界检查的写法另见 [[p:me/python-pitfalls]] 的「边界和差一」。
+- 数组开到 $n + 1$ 格：结果对，但 n 远大于 $|s|$ 时慢几十倍，见「只看走得到的位置」。
 
 ## 能不能不按结尾分开
 
 - 只按位置做一个 dp（每个字符选或不选，`new[p ± 1] += dp[p]`），数的是下标组合，同一个例子得到 20。最小反例：`s = "ll"`、`n = 1`、`x = 1`、`y = 0`，两个 l 都能单独选，下标组合有 2 种，但不同的字符串只有 `"l"` 一个，答案是 1。
-- 也可以写成表面上不分开的样子：`T[p]` 表示所有不同子序列（含空串）停在 p 的个数，再存 `last[c]`，即上一次遇到 c 之前的 `T`。遇到 c 时 `T_new = T + shift_c(T) − shift_c(last[c])`，然后 `last[c] = T`，答案是 `T[y]`（y = x 时减掉空串）。这就是 LC 940 的 `dp[i] = 2·dp[i-1] − dp[last[c]-1]` 加上位置这一维。
+- 也可以写成表面上不分开的样子：`T[p]` 表示所有不同子序列（含空串）停在 p 的个数，再存 `last[c]`，即上一次遇到 c 之前的 `T`。遇到 c 时 `T_new = T + shift_c(T) − shift_c(last[c])`，然后 `last[c] = T`，答案是 `T[y]`（$y = x$ 时减掉空串）。这就是 LC 940 的 `dp[i] = 2·dp[i-1] − dp[last[c]-1]` 加上位置这一维。
 - 但 `shift_c(last[c])` 正好就是旧的 `dp[c]`，所以 `last['l']`、`last['r']` 存的还是那两行信息，内存和计算量都一样。「不分开」只是换了写法，去重这一步省不掉。这个写法也和暴力对拍过。
 
-## 英文讲法
-
-> [!say] Because the question counts distinct subsequences, I track, for each ending character and each position, how many distinct subsequences end there; when I see a character c, every distinct subsequence so far extended by c gives exactly the new set ending in c, so I overwrite that row instead of adding to it.
+2026-10-27 在云端重跑：只按位置的一个 dp 在 `"ll"` 那组上得 2，在题面例子上得 20。`T` 加 `last[c]` 的写法在题面例子上得 7。随机对拍的结果见「测试用例」。
+
+## 测试用例
+
+2026-10-27 在云端 Python 3.13 上跑了「代码」一节的两版，同时跑了两个错误版本和一个暴力解。
+
+- 暴力解枚举所有下标组合，模拟走法，用 `set` 收集合法的字符串，`set` 的大小是「不同串」的答案，合法组合的个数是「按下标」的答案。
+- 加旧值的版本：把窗口版循环里的 `counts = ...` 和 `ends_with[move] = new_row` 两行换成 Follow-up 里「按下标组合数」那三行。
+- 只查终点的版本：一步也不丢状态，等于把数轴两头各放宽 $|s|$ 格再算，写成 `count_distinct_subsequence_walks(s, n + 2 * len(s), x + len(s), y + len(s))`。放宽以后任何走法都不会出界，只有起点和终点还要求在原来的 $[0, n]$ 里（调用前单独检查）。
+
+| 输入 `(s, n, x, y)` | 逐格版 | 窗口版 | 加旧值的版本 | 只查终点的版本 | 暴力（不同串） | 暴力（按下标） |
+| --- | --- | --- | --- | --- | --- | --- |
+| `("rrlrlr", 6, 1, 2)` | 7 | 7 | 20 | 7 | 7 | 20 |
+| `("lr", 2, 0, 0)` | 0 | 0 | 0 | 1 | 0 | 0 |
+
+边界输入（窗口版，暴力的结果相同）：
+
+| 输入 | 输出 | 说明 |
+| --- | --- | --- |
+| `("", 3, 1, 1)` | 0 | 空串不算 |
+| `("rl", 3, 1, 1)` | 1 | `x == y`，走出去再绕回来的 `rl` 算 |
+| `("rr", 0, 0, 0)` | 0 | `n == 0`，一步都走不了 |
+| `("r", 3, 5, 1)` | 0 | 起点在 $[0, n]$ 外 |
+| `("lll", 3, 3, 0)` | 1 | 只有 `lll` |
+| `("rlrl", 1, 0, 0)` | 2 | `rl` 和 `rlrl`，`rr` 这类会出界 |
+
+随机对拍分两组：
+
+- 固定种子 20261027，$|s|$ 取 0 到 12、n 取 0 到 8，`x`、`y` 在 $-1$ 到 $n + 1$ 里随机，共 3000 组。窗口版和暴力（不同串）全部一致，加旧值的版本和暴力（按下标）全部一致。其中 `x`、`y` 都在 $[0, n]$ 里的 1411 组上，逐格版、`T` 加 `last[c]` 的写法都和暴力（不同串）一致，只按位置的一个 dp 和暴力（按下标）一致。
+- $|s| \le 40$、$n \le 60$、`x`、`y` 在 $[0, n]$ 里随机，共 2000 组，逐格版、窗口版、开 $n + 1$ 格的窗口版（`reachable_window` 返回 `(0, n)`）三者全部一致。
+
+## Follow-up
+
+### 如果要按下标组合数呢
+
+题目如果改成不去重，同一个串由不同下标选出来算多次，改法如下。最省事的是「能不能不按结尾分开」第一条那个只按位置的 dp，它数的就是下标组合。手上已经是窗口版的话，只改覆盖的那一步，`ends_with[move]` 由覆盖改成加上挪完的数组：
+
+```python
+added = [(old + new) % MOD for old, new in zip(old_row, new_row)]
+counts = [(total - old + now) % MOD for total, old, now in zip(counts, old_row, added)]
+ends_with[move] = added
+```
+
+这三行替换窗口版循环里的 `counts = ...` 和 `ends_with[move] = new_row` 两行。这时 `ends_with[c][p]` 的意思变成「以 c 结尾、停在 p 的下标组合数」。第 i 个字符是 c 时，以 c 结尾的组合分两类：不用第 i 个字符的（就是旧的 `ends_with[c]`），和用第 i 个字符当最后一个的（前面任意一个组合或空集，再挪一格）。两类不重叠，所以相加。`counts` 也跟着按新的一行更新。「测试用例」里加旧值的版本就是这段，例子得 20，随机对拍全部和按下标的暴力一致。复杂度不变。
+
+> [!say] If we count index choices instead of distinct strings, the subsequences ending at index i are new and disjoint from the old ones, so I add the shifted row to the old row.
+
+### 还要更快：用 numpy 整行算
+
+纯 Python 的瓶颈在 `counts` 那一行列表推导，每格都要解释执行一次减、加、取模。改用 numpy 数组，整行的挪格和加减在 C 里一次做完，算法和窗口都不变：
+
+```python
+import numpy as np
+
+
+def count_distinct_subsequence_walks_np(s, n, x, y):
+    if not (0 <= x <= n and 0 <= y <= n) or abs(x - y) > len(s):
+        return 0
+    lo, hi = reachable_window(n, x, y, len(s))
+    width = hi - lo + 1
+    ends_with = {"l": np.zeros(width, np.int64), "r": np.zeros(width, np.int64)}
+    counts = np.zeros(width, np.int64)
+    counts[x - lo] = 1
+    for move in s:
+        new_row = np.zeros(width, np.int64)
+        if move == "r":
+            new_row[1:] = counts[:-1]
+        else:
+            new_row[:-1] = counts[1:]
+        counts = (counts - ends_with[move] + new_row) % MOD
+        ends_with[move] = new_row
+    return int((ends_with["l"][y - lo] + ends_with["r"][y - lo]) % MOD)
+```
+
+每格的值都小于 $10^9 + 7$，`counts - old + new` 落在 $(-2^{30}, 2^{31})$ 里，`int64` 不会溢出。numpy 的 `%` 对负数也返回非负余数，和 Python 一样。2026-10-27 用 numpy 2.5.3 实测：$|s| = 10^4$、$n = 10^4$ 用 1.46 秒，同一组输入纯 Python 的窗口版用 11.70 秒，答案相同。复杂度表里其余几组也都和纯 Python 版答案相同。随机 2000 组小输入（$|s| \le 40$、$n \le 60$，`x`、`y` 在 $-1$ 到 $n + 1$ 里）和纯 Python 版全部一致。
+
+代价是依赖 numpy。HackerRank 这场测评的 Python 环境能不能 `import numpy` 未核实，交卷前先在平台上试一行 `import numpy`，不能用就交纯 Python 版。
更新题目 l/r 子序列走到 y 的方案数

body

meta
