题意简述

与 Easy Version 相同，但 $k$ 最大可到 $10^{12}$，不能直接循环 $k$ 次。机器人初始在 $(0,0)$，在 $w\times h$ 矩形内移动，碰到墙壁会反转对应方向的指令。脚本连续执行 $k$ 遍，求经过 $(0,0)$ 的总次数（初始点不计）。

环面模型

墙壁反射等价于在一个 $2w \times 2h$ 的环面上运动。坐标始终模 $2w$ 和 $2h$。设 $X$ 为执行一遍脚本后的净水平位移（在环面上模 $2w$），$Y$ 为净垂直位移（模 $2h$）。预处理出脚本每一步 $i$（$1 \le i \le n$）后的坐标 $(x_i, y_i)$（均在 $[0,2w)$ 和 $[0,2h)$ 内）。

第 $j$ 遍（$0 \le j < k$）的第 $i$ 步后，机器人的环面坐标为：

$$(x_i + j \cdot X \bmod 2w,\; y_i + j \cdot Y \bmod 2h) $$

我们需要其等于 $(0,0)$，即：

$$j \cdot X \equiv -x_i \pmod{2w}, \quad j \cdot Y \equiv -y_i \pmod{2h} $$

线性同余方程求解

对每个固定的 $i$，分别解出 $j$ 满足两个同余方程的通解。

第一个方程 $j \cdot X \equiv -x_i \pmod{2w}$：

• 设 $g_x = \gcd(X, 2w)$。若 $-x_i \bmod g_x \neq 0$，则无解。
• 否则存在最小非负解 $cx$，且解的形式为 $j \equiv cx \pmod{W}$，其中 $W = 2w / g_x$。

第二个方程 $j \cdot Y \equiv -y_i \pmod{2h}$：

• 同理，若解存在，最小解为 $cy$，周期为 $H = 2h / \gcd(Y, 2h)$。

合并两个解

现在需要 $j$ 同时满足 $j \equiv cx \pmod{W}$ 和 $j \equiv cy \pmod{H}$。使用中国剩余定理（CRT）合并：

• 如果 $\gcd(W, H) \nmid (cy - cx)$，则无解。
• 否则存在最小非负解 $result$，且解周期为 $L = \operatorname{lcm}(W, H)$。

在范围 $0 \le j < k$ 内，解的个数为：

$$\max\left(0,\; \left\lfloor \frac{k - 1 - result}{L} \right\rfloor + 1 \right) $$

（若 $result \ge k$ 则为 $0$）。

对所有 $i = 1 \dots n$ 累加即得最终答案。

复杂度

预处理 $O(n)$。对每个 $i$ 进行一次 exgcd 和 CRT，总复杂度 $O(n \log \max(w,h))$。由于 $\sum n \le 10^6$，足以通过。

参考代码

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

using ll = long long;

// 自定义 gcd 和 lcm
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

namespace CRT {    
    // v * inv(v, M) = 1 (mod M)
    ll inv(ll v, ll M) {
        ll a = 1, b = 0;
        for (ll x = v, y = M; x != 0; ) {
            swap(a, b -= y/x * a);
            swap(x, y -= y/x * x);
        }
        return b + (b<0) * M;
    }

    // 求最小的 x 使得 a*x = b (mod c)
    ll solve_1(ll a, ll b, ll c) {
        ll g = gcd(a, c);
        if (b % g != 0) return -1;
        return b/g * inv(a/g, c/g) % (c/g);
    }

    // 求最小的 x 满足 x % b = a 且 x % d = c
    ll solve_2(ll a, ll b, ll c, ll d) {
        ll t = (c-a)%d;
        if (t < 0) t += d;
        ll k = solve_1(b, t, d);
        return k==-1 ? -1 : a + k*b;
    }
}

const int N = 1e6 + 5;

ll n, k, w, h;
ll x[N], y[N];

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int tc; cin >> tc;
    while (tc--) {
        string s;
        cin >> n >> k >> w >> h >> s;

        for (int i = 1; i <= n; i++) {
            x[i] = x[i-1] + (s[i-1] == 'R') - (s[i-1] == 'L');
            y[i] = y[i-1] + (s[i-1] == 'U') - (s[i-1] == 'D');
            x[i] += (x[i] < 0) * 2*w - (x[i] >= 2*w) * 2*w;
            y[i] += (y[i] < 0) * 2*h - (y[i] >= 2*h) * 2*h;
        }

        ll ww = 2*w / gcd(x[n], 2*w);
        ll hh = 2*h / gcd(y[n], 2*h);
        ll ans = 0, L = lcm(ww, hh);

        for (int i = 1; i <= n; i++) {
            ll cx = CRT::solve_1(x[n], (2*w - x[i]) % (2*w), 2*w);
            ll cy = CRT::solve_1(y[n], (2*h - y[i]) % (2*h), 2*h);
            if (cx == -1 || cy == -1) continue;

            ll result = CRT::solve_2(cx, ww, cy, hh);
            if (result != -1 && result < k) {
                ans += (k - result - 1) / L + 1;
            }
        }

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