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

题目 visa-lr-subsequence-moves · 修改（rev 6） · user · 2026-10-26 19:38
body

@@ -21,9 +21,10 @@
 - `p`：从 `x` 出发按这个子序列走完，停在哪个位置。
 
-`end[i][c][p]` 表示：在 `s` 前 i 个字符能选出的所有不同子序列里，以 c 结尾、走完停在 p 的有几个。i = 0 时还没有非空子序列，所有格子都是 0。处理第 i 个字符 `ch = s[i]`（下标从 0 开始）时，分三步：
+`end[i][c][p]` 表示：在 `s` 前 i 个字符能选出的所有不同子序列里，以 c 结尾、走完停在 p 的有几个。i = 0 时还没有非空子序列，所有格子都是 0。处理第 i 个字符 `ch = s[i]`（下标从 0 开始）时，分两步：
 
-1. 先算「前 i 个字符的所有不同子序列停在 p 的个数」`all_i[p] = (p == x ? 1 : 0) + end[i]['l'][p] + end[i]['r'][p]`，那个 1 是空串（还停在起点）。
-2. 以 `ch` 结尾的那一行整行重算：把 `all_i` 往 `ch` 的方向挪一格，得到 `end[i+1][ch][q] = all_i[p]`，其中 q 是 p 挪一格后的位置，越界的丢掉。这一行只由 `all_i` 决定，和 `end[i][ch]` 原来的值无关，这就是上面说的「覆盖」。
-3. 结尾字符不是 `ch` 的那一行原样继承：`end[i+1][c'][p] = end[i][c'][p]`（`c' ≠ ch`）。原因是用到 `s[i]` 的子序列，`s[i]` 一定是最后一个字符，这样的子序列都以 `ch` 结尾，所以以 c' 结尾的不同子序列和处理 `s[i]` 之前完全一样。
+1. 重算以 `ch` 结尾的计数，也就是 `end[i+1][ch][p]`，p 取 0 到 n 的每一个位置。分两小步：
+   1. 先算「前 i 个字符的所有不同子序列停在 p 的个数」`all_i[p] = (p == x ? 1 : 0) + end[i]['l'][p] + end[i]['r'][p]`，那个 1 是空串（还停在起点）。
+   2. 把 `all_i` 往 `ch` 的方向挪一格，得到 `end[i+1][ch][q] = all_i[p]`，其中 q 是 p 挪一格后的位置，越界的丢掉。新算出的 `end[i+1][ch][·]` 只由 `all_i` 决定，和 `end[i][ch]` 原来的值无关，这就是上面说的「覆盖」。
+2. 结尾字符不是 `ch` 的计数原样继承：对每个位置 p，`end[i+1][c'][p] = end[i][c'][p]`（`c' ≠ ch`）。原因是用到 `s[i]` 的子序列，`s[i]` 一定是最后一个字符，这样的子序列都以 `ch` 结尾，所以以 c' 结尾的不同子序列和处理 `s[i]` 之前完全一样。
 
 最后答案是 `end[|s|]['l'][y] + end[|s|]['r'][y]`，空串不在里面，正好满足「非空」。
@@ -31,7 +32,7 @@
 ### 压缩掉 i 这一维
 
-第 i+1 层只用到第 i 层，所以只留一层 `end[c][p]`，每处理一个字符就把它更新成下一层。滚动以后，第 3 步的「原样继承」什么都不用做，剩下的就是第 1、2 步：算出 `all_`，往 `ch` 的方向挪一格，覆盖 `end[ch]`。空间从三维表的 O(|s| · n) 降到 O(n)。
+第 i+1 层只用到第 i 层，所以只留一层 `end[c][p]`，每处理一个字符就把它更新成下一层。滚动以后，第 2 步的「原样继承」什么都不用做，剩下的就是第 1 步：算出 `all_`，往 `ch` 的方向挪一格，覆盖 `end[ch]`。空间从三维表的 O(|s| · n) 降到 O(n)。
 
-在第 1 步读到的全是上一层的值的前提下，压缩以后结果不变。下面的代码先用旧的 `end` 把 `all_` 整个算完，再把挪格的结果写进新数组 `new`，最后才赋给 `end[ch]`，所以满足这个前提。如果 `all_` 还没算完就往 `end[ch]` 里写，`all_` 就会读到这一层刚写进去的值，等于把第 i+1 层和第 i 层混在一起用了。
+在算 `all_` 时读到的全是上一层的值的前提下，压缩以后结果不变。下面的代码先用旧的 `end` 把 `all_` 整个算完，再把挪格的结果写进新数组 `new`，最后才赋给 `end[ch]`，所以满足这个前提。如果 `all_` 还没算完就往 `end[ch]` 里写，`all_` 就会读到这一层刚写进去的值，等于把第 i+1 层和第 i 层混在一起用了。
 
 ## 代码