题意简述

机器人从 $(0,0)$ 出发，在 $w \times h$ 矩形内移动，碰到边界时会反转对应方向的指令（所有 L/R 互换，或所有 U/D 互换），并从那一步重新开始。脚本 $s$ 连续执行 $k$ 次（$k \le n$），求总共有多少次经过 $(0,0)$（初始点不计）。

关键观察

反射边界等价于在一个大小为 $2w \times 2h$ 的环面上运动。具体而言，对横坐标模 $2w$，纵坐标模 $2h$，可以将机器人的真实位置映射到环面上的一个点。机器人每一步移动后，其在环面上的坐标都是确定的，且不依赖反射的具体发生。

因此，整个问题可以转化为：

• 执行一遍脚本 $s$（$n$ 步），记录每一步移动后在环面上的坐标 $(x_i, y_i)$，并统计每个坐标出现的次数（哈希表 cnt）。
• 设一遍脚本的净位移（在环面上）为 $(dx, dy)$（即循环结束后坐标的模余数）。则第 $i$ 遍（$i$ 从 $0$ 到 $k-1$）执行前，机器人的起始环面坐标为 $(i \cdot dx \bmod 2w, i \cdot dy \bmod 2h)$。
• 在第 $i$ 遍中，某一步的环面坐标等于该步的 $(x_j, y_j)$ 加上起始偏移。要使其等于 $(0,0)$，需要满足：$$x_j + i \cdot dx \equiv 0 \pmod{2w}, \quad y_j + i \cdot dy \equiv 0 \pmod{2h} $$也就是：$$x_j \equiv -i \cdot dx \pmod{2w}, \quad y_j \equiv -i \cdot dy \pmod{2h} $$
• 所以对于每个 $i$，我们只需在哈希表中查找键值 $\left((-i \cdot dx \bmod 2w), (-i \cdot dy \bmod 2h)\right)$ 对应的计数，累加到答案即可。

复杂度

• 对每组数据，遍历脚本一遍 $O(n)$，哈希表操作 $O(n)$。
• 枚举 $i$ 从 $0$ 到 $k-1$ 共 $k$ 次，每次 $O(1)$ 查询。由于 $k \le n$，总复杂度 $O(n)$。
• 总时间复杂度 $O(\sum n) \le 10^6$，完全可行。

参考代码

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

using ll = long long;
const int N = 1e6 + 5;

string s;
ll n, k, w, h;
ll tx[2*N], ty[2*N];
map<pair<ll, ll>, ll> cnt;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int t;
    cin >> t;

    while (t--) {
        cin >> n >> k >> w >> h >> s;

        cnt.clear();
        ll x = 0, y = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == 'L') x--;
            if (s[i] == 'R') x++;
            if (s[i] == 'D') y--;
            if (s[i] == 'U') y++;

            x = (x + 2*w) % (2*w);
            y = (y + 2*h) % (2*h);
            cnt[{x, y}]++;
        }

        ll ans = 0;
        for (int i = 0; i < k; i++) {
            ll vx = (-i*x%(2*w) + 2*w)%(2*w);
            ll vy = (-i*y%(2*h) + 2*h)%(2*h);
            ans += cnt[{vx, vy}];
        }

        cout << ans << '\n';
    }
}