P14445 Follow the Sequence 解题记录：从“无限复制路径”到“离散射线”

1. 题目详情

原题链接：P14445 [ICPC 2025 Xi'an Practice] Follow the Sequence

给定一个由构成的字符串，将它无限重复，并从原点开始按照指令移动。之后给出 $m$ 个关键点，要求统计其中有多少个会在无限行走过程中被访问。

所有测试用例的 $\sum n,\sum m\le 5\times 10^5$ ，关键点坐标范围为 $[-10^9,10^9]$ 。原题还特别说明：即使多个关键点坐标相同，它们仍然被视为不同的关键点，因此查询需要逐个计数，不能对输入点去重。

2. 题目简述

字符串只包含一轮移动，但这轮移动会被无限重复。

例如，一轮结束后总位移为

D=(d_x,d_y).

设一轮内，在执行前 $i$ 条指令后所在的位置为

P_i=(x_i,y_i).

那么经过 $k$ 个完整周期，再执行前 $i$ 条指令时，位置一定是

P_i+kD.

因此整个无限行走过程中访问到的点为

\bigcup_{i=0}^{n-1} \left\{ P_i+kD\mid k\in\mathbb Z_{\ge 0} \right\}.

题目要求判断每个给定点是否属于这个集合。

3. 最开始的错误思路

最开始，我已经注意到每个周期都会产生相同的总位移

D=(d_x,d_y).

于是尝试按照坐标余数给关键点编码，例如：

x\bmod |d_x|,\qquad y\bmod |d_y|.

然后：

将所有关键点按照余数编码排序；
枚举第一轮内经过的每个位置；
找到与当前前缀位置编码相同的关键点；
再判断坐标差是不是总位移的整数倍。

这个想法看起来似乎已经将无限问题变成了有限问题，而且还可以通过排序定位同类关键点。

但它的根本问题是：

余数编码只是一个很弱的必要条件，并没有真正表示路径的结构。

例如当

d_x=d_y=1

时，所有整数坐标对 $1$ 取模都等于 $0$ 。于是所有关键点都进入同一个桶，一轮中的每个前缀位置也都会找到这个桶。

最坏情况下就会变成：

O(nm).

即使 $d_x,d_y$ 不是 $1$ ，同一个余数桶中也可能存在大量处于不同平行线上的点。

所以问题不是简单的代码实现错误，而是：

编码没有把真正决定可达性的结构表达出来。

负数取模、某一维总位移为零、初始原点没有处理等，虽然也会造成错误，但这些只是实现层面的问题。更深层的问题是，这个模型没有保证一个桶对应一条真正的运动轨道。

后来我又尝试根据单轮路径的包围范围建立坐标系，为单轮位置分配唯一编号。但这仍然是在研究“路径如何复制”，没有解决查询点到底属于哪一条无限轨道的问题。

4. 真正卡住的地方：没有寻找结构性

这道题真正困难的地方并不是某个复杂的数据结构，而是没有足够快地发现它的结构。

我之前一直在思考：

第一轮路径应该如何向后扩张、复制和编码？

但更有效的问题应该是：

给定一个关键点 $Q$ ，怎样证明它能够被访问？

这是两种完全不同的视角。

前者是生成视角：试图构造无限路径。

后者是判定视角：试图给出一个点可达的充要条件。

一旦从判定角度思考，答案几乎会自动出现。

一个关键点 $Q$ 可达，当且仅当存在某个单轮前缀位置 $P_i$ 和某个非负整数 $k$ ，使得

\boxed{Q=P_i+kD}.

这就是完整的充要条件。

题目中的无限字符串、连续移动、路径复制，最终都被压缩成了这一条式子。

什么是这道题的“结构性”？

这里的结构性是：

每一轮路径都不是任意变化，而是上一轮路径整体平移同一个向量 $D$ 。

因此，题目可以拆成两个有限部分：

一轮内的形状，由 $P_0,P_1,\ldots,P_{n-1}$ 表示；
轮与轮之间的变化，由固定向量 $D$ 表示。

对固定的一个前缀位置 $P_i$ ，它在后续周期中对应的位置是

P_i,\quad P_i+D,\quad P_i+2D,\quad\ldots

这不是一条复杂路径，而是一条沿 $D$ 方向延伸的离散射线。

所以整个答案集合其实是：

至多 $n$ 条方向相同的离散射线的并集。

这才是题目的真实模型。

5. 用一个小例子看出答案集合

假设一轮指令是：

text

URR

那么一轮中的前缀位置是：

P_0=(0,0),\quad P_1=(0,1),\quad P_2=(1,1).

一轮总位移为

D=(2,1).

三个前缀位置分别产生：

text

P0: (0,0), (2,1), (4,2), (6,3), ...
P1: (0,1), (2,2), (4,3), (6,4), ...
P2: (1,1), (3,2), (5,3), (7,4), ...

如果只看移动过程，它像一条不断延伸的折线路径。

但如果把结果集合画出来，会发现它实际上就是三条平行的离散射线。

这说明可视化时不应该只画“一条路径怎么走”，而应该：

画出第一轮；
将第一轮沿 $D$ 平移两三次；
暂时忽略点之间的行走顺序；
观察所有访问点形成了什么集合。

这样，“若干条平行射线”的结构会非常明显。

6. 正确思路

设一轮总位移为

D=(d_x,d_y).

对于固定前缀位置

P=(x,y),

它生成的点为

P+kD,\qquad k\ge 0.

判断一个查询点 $Q$ 是否属于这条射线，需要解决三个问题：

$Q$ 和 $P$ 是否位于同一条平行于 $D$ 的直线上；
$Q-P$ 是否是完整总位移 $D$ 的整数倍；
这个整数倍是否非负。

我们分别对这三部分编码。

6.1 判断是不是同一条直线

先考虑

d_x\ne 0.

所有射线的斜率都是

\frac{d_y}{d_x}.

经过点 $(x,y)$ 的直线可以写成

y=\frac{d_y}{d_x}x+c.

为了避免浮点数和分数，将等式乘以 $d_x$ ：

d_xy-d_yx=d_xc.

因此定义

\boxed{b=d_xy-d_yx}.

对于同一条平行线上的所有点， $b$ 都相同。

如果点移动一个周期：

(x,y)\rightarrow(x+d_x,y+d_y),

那么

\begin{aligned} b' &=d_x(y+d_y)-d_y(x+d_x)\\ &=d_xy+d_xd_y-d_yx-d_yd_x\\ &=d_xy-d_yx\\ &=b. \end{aligned}

所以 $b$ 就是这条直线的编号，也可以理解为经过整数放大后的截距。

它同时处理了：

正斜率；
负斜率；
水平线；
分数斜率。

6.2 在同一直线上仍然不一定可达

只判断直线还不够。

例如总位移为

D=(2,4).

点

(0,0)

和

(1,2)

在同一条直线上，但从 $(0,0)$ 出发，每次只能增加 $(2,4)$ ，不可能恰好到达 $(1,2)$ 。

所以还要判断：

Q-P

是不是完整的 $D$ 的整数倍。

当 $d_x\ne 0$ 时，每执行一个周期，横坐标增加 $d_x$ 。因此同一条离散轨道上的点必然满足

x_Q\equiv x_P\pmod {|d_x|}.

定义

\boxed{r=x\bmod |d_x|}.

负数取模需要规范到

[0,|d_x|-1]

内。

于是：

\boxed{(b,r)}

唯一确定一条离散轨道。

为什么它是充分的？

如果两个点的 $b$ 相同，并且横坐标余数相同，那么存在整数 $k$ ，使得

x_Q-x_P=kd_x.

又因为 $b$ 相同：

d_xy_Q-d_yx_Q=d_xy_P-d_yx_P.

整理得到

d_x(y_Q-y_P)=d_y(x_Q-x_P).

代入

x_Q-x_P=kd_x

可得

y_Q-y_P=kd_y.

所以

Q-P=kD.

6.3 判断方向是否正确

即使

Q-P=kD

中的 $k$ 是整数，也还要满足

k\ge 0.

因为路径只能沿总位移方向继续前进，不能回到负周期。

当 $d_x>0$ 时，每个周期横坐标变大，所以要求

x_Q\ge x_P.

当 $d_x<0$ 时，每个周期横坐标变小，所以要求

x_Q\le x_P.

统一定义

\operatorname{dir}= \begin{cases} 1,&d_x>0,\\ -1,&d_x<0, \end{cases}

以及

\boxed{\operatorname{pos}=\operatorname{dir}\cdot x}.

每执行一个周期，都会增加

|d_x|.

于是方向条件统一变为：

\boxed{\operatorname{pos}_Q\ge \operatorname{pos}_P}.

7. 多个相同轨道如何压缩

一轮内可能有多个前缀位置拥有相同的

(b,r).

这说明它们处于同一条离散轨道上。

假设两个起点的方向坐标分别是

\operatorname{pos}_1<\operatorname{pos}_2.

那么从第一个点产生的射线已经覆盖了第二个点产生的全部射线：

\{\operatorname{pos}_1+k|d_x|\mid k\ge 0\}

包含

\{\operatorname{pos}_2+k|d_x|\mid k\ge 0\}.

因此，对于每个

(b,r)

只需要保存最小的。

我们可以将所有前缀点编码成：

cpp

{b, r, pos}

然后按照

text

b -> r -> pos

排序。

相同 $(b,r)$ 的第一个元素必然拥有最小，所以直接去重即可。

查询时计算关键点的

text

b、r、pos

二分查找对应的 $(b,r)$ ，然后判断：

cpp

query_pos >= minimum_pos

即可。

8. 竖直方向的特殊情况

当

d_x=0,\quad d_y\ne 0

时，斜率不存在，所有射线都是竖直线。

此时：

同一条直线要求 $x$ 相同，因此令

b=x;

每个周期纵坐标增加 $d_y$ ，因此令

r=y\bmod |d_y|;

方向坐标为

\operatorname{pos}=\operatorname{sign}(d_y)\cdot y.

后续的排序、去重和查询过程完全相同。

这比单独讨论“正斜率、负斜率、斜率不存在”更简单。实际上只需要区分：

$d_x\ne 0$ ：使用横坐标判断周期倍数；
$d_x=0$ ：使用纵坐标判断周期倍数。

9. 总位移为零

如果

D=(0,0),

那么执行完整个字符串后又回到原点。

此时所有周期访问的点完全相同，答案集合就是第一轮中的：

P_0,P_1,\ldots,P_{n-1}.

将这些坐标排序去重，然后对每个关键点二分查找即可。

注意应该记录

P_0,P_1,\ldots,P_{n-1},

而不是必须额外记录 $P_n$ 。

因为

P_n=D=P_0+D

已经是下一周期的 $P_0$ 。

代码中最自然的写法是：

cpp

先记录当前位置；
再执行当前指令。

这样会恰好记录所有需要的前缀位置，并包含初始原点。

10. 完整代码

下面使用纯，不与混用。

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 500000 + 5;

char s[MAXN];

struct Node {
    ll b;
    ll r;
    ll pos;

    bool operator < (const Node &other) const {
        if (b != other.b) return b < other.b;
        if (r != other.r) return r < other.r;
        return pos < other.pos;
    }
};

ll norm_mod(ll x, ll mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

void move_point(char c, ll &x, ll &y) {
    if (c == 'U') {
        ++y;
    } else if (c == 'D') {
        --y;
    } else if (c == 'L') {
        --x;
    } else {
        ++x;
    }
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int n, m;
        scanf("%d%d%s", &n, &m, s);

        ll dx = 0;
        ll dy = 0;

        for (int i = 0; i < n; ++i) {
            move_point(s[i], dx, dy);
        }

        ll answer = 0;

        /*
            总位移为 (0,0)：
            只会重复访问第一轮中的位置。
        */
        if (dx == 0 && dy == 0) {
            vector<pair<ll, ll>> points;
            points.reserve(n);

            ll x = 0;
            ll y = 0;

            // 记录 P0, P1, ..., P(n-1)
            for (int i = 0; i < n; ++i) {
                points.push_back({x, y});
                move_point(s[i], x, y);
            }

            sort(points.begin(), points.end());

            points.erase(
                unique(points.begin(), points.end()),
                points.end()
            );

            while (m--) {
                ll p, q;
                scanf("%lld%lld", &p, &q);

                if (binary_search(
                    points.begin(),
                    points.end(),
                    make_pair(p, q)
                )) {
                    ++answer;
                }
            }

            printf("%lld\n", answer);
            continue;
        }

        vector<Node> lines;
        lines.reserve(n);

        bool vertical = (dx == 0);

        /*
            dx != 0 时使用 x：
                b = dx * y - dy * x
                r = x mod |dx|

            dx == 0 时使用 y：
                b = x
                r = y mod |dy|
        */
        ll d = vertical ? dy : dx;
        ll step = llabs(d);
        ll direction = (d > 0 ? 1 : -1);

        ll x = 0;
        ll y = 0;

        for (int i = 0; i < n; ++i) {
            ll b;
            ll z;

            if (vertical) {
                b = x;
                z = y;
            } else {
                b = dx * y - dy * x;
                z = x;
            }

            lines.push_back({
                b,
                norm_mod(z, step),
                direction * z
            });

            move_point(s[i], x, y);
        }

        sort(lines.begin(), lines.end());

        /*
            相同 (b,r) 的元素按照 pos 升序排列，
            只保留最小 pos。
        */
        int count = 0;

        for (int i = 0; i < (int)lines.size(); ++i) {
            if (
                count == 0 ||
                lines[count - 1].b != lines[i].b ||
                lines[count - 1].r != lines[i].r
            ) {
                lines[count++] = lines[i];
            }
        }

        lines.resize(count);

        while (m--) {
            ll p, q;
            scanf("%lld%lld", &p, &q);

            ll b;
            ll z;

            if (vertical) {
                b = p;
                z = q;
            } else {
                b = dx * q - dy * p;
                z = p;
            }

            ll r = norm_mod(z, step);
            ll pos = direction * z;

            Node key{b, r, LLONG_MIN};

            auto it = lower_bound(
                lines.begin(),
                lines.end(),
                key
            );

            if (
                it != lines.end() &&
                it->b == b &&
                it->r == r &&
                pos >= it->pos
            ) {
                ++answer;
            }
        }

        printf("%lld\n", answer);
    }

    return 0;
}

11. 复杂度分析

对一轮中的 $n$ 个前缀位置排序：

O(n\log n).

每个关键点进行一次二分查询：

O(\log n).

所以单个测试用例的总复杂度为

\boxed{O(n\log n+m\log n)}.

空间复杂度为

\boxed{O(n)}.

由于所有测试用例的 $\sum n,\sum m\le 5\times10^5$ ，该复杂度可以通过。

12. 怎样在考场上更快发现这个模型？

这次真正的问题不是“不会优化”，而是在找到充分性质之前就急于开始设计编码。

以后遇到类似问题，可以强制自己完成下面几个步骤。

第一步：把无限过程写成公式

看到“某段操作无限重复”，第一反应应该是：

执行完整一轮后，状态发生了什么固定变化？

本题中，完整一轮后只是平移

D=(d_x,d_y).

因此立刻写出：

\boxed{\text{第 }kn+i\text{ 步的位置}=P_i+kD}.

只要这条式子写出来，题目的无限性就已经消失了一大半。

第二步：从生成视角切换到判定视角

不要继续问：

路径会如何不断扩张？

而要问：

给定一个答案点 $Q$ ，它可达的充要条件是什么？

本题就是：

\boxed{\exists i,\ k\ge 0,\quad Q=P_i+kD}.

这个式子会直接告诉我们需要检查：

是否属于同一条直线；
差是否是完整周期位移的整数倍；
方向是否正确。

数据结构应该从充要条件中产生，而不是先想一个编码，再尝试证明它有效。

第三步：固定一个变量，观察剩余集合

式子中有两个变量：

i,\quad k.

先固定 $i$ 。

那么

P_i+kD

随着 $k$ 变化形成什么？

它形成一条离散射线。

于是原题就从：

一条无限复杂路径

变成了：

$n$ 条平行离散射线的并。

这一步是模型出现的关键。

第四步：可视化结果集合，而不是只可视化过程

手动画图时，不应该只画箭头和行走顺序。

更有效的方法是：

画出第一轮的所有前缀点；
计算总位移 $D$ ；
将这些点整体平移 $D$ 和 $2D$ ；
暂时擦掉点之间的连线；
只观察所有访问点组成的集合。

很多周期问题的结构，在“过程图”中并不明显，但在“答案集合图”中会非常明显。

本题只要画两三个周期，就很容易看到若干条平行射线。

第五步：检查编码是充要条件还是必要条件

最初的余数编码之所以危险，是因为它只满足：

\text{可达}\Longrightarrow\text{余数相同},

却没有直接满足：

\text{余数相同}\Longrightarrow\text{可达}.

考场上设计完一个分类方式后，应立即问：

两个被编码到同一组的点，是否一定属于同一条运动轨道？

如果不是，那么这一组可能非常大，后面可能还需要枚举，复杂度也可能退化。

本题最终的

(b,r)

则是完整的轨道编号：

(b,r)\text{ 相同} \iff Q-P=kD,\quad k\in\mathbb Z.

再加入方向比较，才得到真正的可达性。

13. 从出题人的角度看题目

从出题人的角度反推，也能更快排除错误方向。

题目提供了几个非常明显的信号：

行走过程无限进行；
关键点坐标可达到 $10^9$ ；
$n,m$ 的总规模达到 $5\times10^5$ ；
只询问有限个关键点是否被访问。

这意味着预期算法不可能真正展开路径。

出题人更可能希望我们做到：

用长度为 $n$ 的第一轮路径建立有限模型；
将每个查询点转换成某种标准形式；
通过排序、二分或哈希快速判断。

而一轮结束后的唯一全局变化就是固定平移 $D$ 。

因此一个自然的出题过程可能是：

先构造若干个前缀点；
让每个前缀点沿同一个向量无限平移；
询问给定点是否属于这些离散射线；
最后再把它包装成的无限字符串。

从这个角度看，题目并不是一道“无限路径模拟题”，而是一道被移动字符串包装起来的：

平行离散射线并集上的点查询问题。

14. 本题复盘

这次没有快速完成，并不是因为正确算法本身复杂。

真正的问题是：

在性质推导还不充分时，过早进入了编码和实现阶段。

我一直盯着路径如何扩张、如何复制、如何将复制后的点分桶，却没有首先逆向回答：

\text{一个点可达，当且仅当什么？}

一旦写出

Q=P_i+kD,

后面的结构就会自然出现：

\text{无限路径} \longrightarrow \text{有限前缀点} + \text{固定平移}

\longrightarrow \text{若干条离散射线}

\longrightarrow \text{直线编号} + \text{离散余数} + \text{方向起点}.

这道题最值得保留的并不是某一个或某一种截距编码，而是下面这个习惯：

面对无限重复过程，先寻找“一轮后的固定变换”；面对点查询，先从答案有效性的充要条件逆向建模；面对不明显的结构，优先画出答案集合，而不是只追踪生成过程。

算法最终很简单，但模型必须先被看见。