模加数组到目标：有限余数状态BFS

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 模数M正整数，可重复使用任一整数操作，start/target先取模，负数按非负余数规范。
• 操作集可能空，零操作不会改变状态；不限定次数或不同操作只能一次。

解题路线

1. 余数0..M−1作节点，u→(u+op)%M，每边一次操作，BFS首次到target最少步。ops先mod去重，减重复边。
2. visited入队即标，起点等target返回0。穷尽仍没目标返回−1，不能因无限实际整数看似无界而不停止。
3. gcd(M,所有op)给可达余数必要且在重复生成有限群合同下充分的差值约束，但它不是最短步数公式；仍用BFS或针对规模的另一证明。

手动走一遍

M7、ops2，从0到1，0→2→4→6→1四步。M6、ops2，0无法到1；ops0且start≠target不可达。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque

def minimum_steps(start,target,operations,modulus):
    if modulus<=0:raise ValueError("positive modulus")
    start%=modulus;target%=modulus;ops={x%modulus for x in operations};distance={start:0};queue=deque([start])
    while queue:
        u=queue.popleft()
        if u==target:return distance[u]
        for op in ops:
            v=(u+op)%modulus
            if v not in distance:distance[v]=distance[u]+1;queue.append(v)
    return -1

复杂度

M状态D不同余数操作，O(MD)时间/O(M+D)空间。M极大时状态数组/字典仍可能不可行，需给范围预算。

易错点与追问

容易失分的边界

• 用普通整数加法不取mod会无限搜索。
• 只用gcd可达判断却直接给出最少步数。

继续深挖

• 每操作代价不同如何转Dijkstra？
• 操作最多各一次时状态为何需要额外使用集合？