题目

CF2145F。

思路

首先，设当前经过了 ss 步，并且令 a0=an,b0=bna_0=a_n,b_0=b_n，那么题目的意思可以翻译为：

当 s mod n=js\bmod n=j 时，所有 x≡bj(modaj)x\equiv b_j\pmod{a_j} 的 xx 会不能走，s=0s=0 时除外。

由于 aia_i 的范围是 2∼102\sim 10，而它们的 LCM 是 M=2520M=2520，所以 0∼M0\sim M 和 M∼2MM\sim 2M 等等的状态是相同的。

所以，我们把每一个点 xx 分出 nn 个状态来，其中 (x,j)(x,j) 表示走到点 xx 时 s mod n=js\bmod n=j。

显然，所有 x≡bj(modaj)x\equiv b_j\pmod{a_j} 的点都是不可到达的。对于可到达的点，我们可以这样造边：

(x,j)→(x+1,(j+1) mod n)(x,j)→(x,(j+1) mod n)(x,j)\to (x+1,(j+1)\bmod n)\\ (x,j)\to (x,(j+1)\bmod n)

这些边的长度都是 11，因此可以通过 BFS 求出最短路 disx,jdis_{x,j}。

当 m<Mm<M 时，自然 min⁡j=0n−1dism,j\min_{j=0}^{n-1}dis_{m,j} 就是答案。当 m≥Mm\ge M 时，我们需要另外讨论。

不难发现，虽然 0∼M,M∼2M0\sim M,M\sim 2M 的状态是相同的，但是我们起始时间对 nn 的模是不一定的。

于是，可以设 Gi,jG_{i,j} 表示起始时间  mod n=i\bmod n=i，到 MM 点时的时间  mod n=j\bmod n=j。

这从实现上来说，只是将起始点从 (0,0)(0,0) 变成了 (0,i)(0,i)，别的都没有什么变化。

然后我们考虑 Gi,j2G^2_{i,j} 表示 0∼2M0\sim 2M 的对应起始和结束时间，考虑能否通过 Gi,jG_{i,j} 得到：

显然，我们可以有这样的式子：

Gi,j2=min⁡k=0n−1{Gi,k+Gk,j}G^2_{i,j}=\min_{k=0}^{n-1} \{G_{i,k}+G_{k,j}\}

这是符合 Flyod 矩阵的定义的，于是主要的问题我们已经解决了，接下来具体实现上还有一些细节。

实现

对于 (0,0)(0,0) 这个点，如果真的是起始点，根据题目的定义，它不会是陷阱；但是如果是 (kM,0)(kM,0) 它就有可能是陷阱。所以我们做 BFS 的时候需要特判这种情况，并且令最开始的矩阵是特殊的 G0G_0；其次，对于一个 mm，它并不一定正好是 MM 的倍数，我们需要关心 m mod Mm\bmod M 的这一段。事实上，我们只需要记录 Hi,j=dism mod M,jH_{i,j}=dis_{m\bmod M,j}，那么最终乘起来的矩阵是：

R=G0×G⌊m/M⌋−1×HR=G_0\times G^{\lfloor m/M\rfloor-1}\times H

答案是 min⁡j=0n−1R0,j\min_{j=0}^{n-1} R_{0,j}。

由于需要多次调用 BFS，所以我们通过时间戳的方式来标记某个点是否到达，这样可以不用每次都清空 vis 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;
const int M = 2520, N = 11;
int n, m, a[N], b[N];

template<typename T>
void chmin(T& v, T x) {
    v = min(v, x);
}

struct Matrix {
    int dat[N][N];

    Matrix() {
        memset(dat, 0, sizeof dat);
    }

    Matrix operator*(const Matrix& mat) const {
        Matrix res;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res.dat[i][j] = INF;
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++)
                for (int j = 0; j < n; j++)
                    chmin(res.dat[i][j], dat[i][k] + mat.dat[k][j]);
        return res;
    }

    Matrix pow(int k) const {
        Matrix res;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res.dat[i][j] = INF;
        for (int i = 0; i < n; i++) res.dat[i][i] = 0;
        Matrix a = *this;
        while (k) {
            if (k & 1) res = res * a;
            a = a * a;
            k >>= 1;
        }
        return res;
    }
};

struct Point {
    int i, j;

    bool valid() {
        return i % a[j] != b[j];
    }
};
int vis[M+1][N];
int dis[M+1][N];
bool trap[M+1][N];

void bfs(Point start, bool specialStart) {
    static int ts;
    ++ts;
    queue<Point> q;
    q.push(start);

    for (int i = 0; i <= M; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = INF;
    if (!start.valid() && !specialStart) {
        return;
    }

    dis[start.i][start.j] = 0;

    while (q.size()) {
        Point t = q.front();
        q.pop();
        if (vis[t.i][t.j] == ts) continue;

        vis[t.i][t.j] = ts;

        Point nxt = {t.i, (t.j+1) % n};
        if (nxt.valid()) {
            chmin(dis[nxt.i][nxt.j], dis[t.i][t.j] + 1);
            q.push(nxt);
        }

        if (t.i+1 <= M) {
            nxt = {t.i+1, (t.j+1) % n};
            if (nxt.valid()) {
                chmin(dis[nxt.i][nxt.j], dis[t.i][t.j] + 1);
                q.push(nxt);
            }
        }
    }
}

int solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    a[0] = a[n], b[0] = b[n];

    if (m < M) {
        bfs({0, 0}, true);
        int ans = INF;
        for (int j = 0; j < n; j++) {
            chmin(ans, dis[m][j]);
        }
        return ans;
    }

    Matrix G, H, G0;

    bfs({0, 0}, true);
    for (int k = 0; k < n; k++) {
        G0.dat[0][k] = dis[M][k];
    }

    for (int j = 0; j < n; j++) {
        bfs({0, j}, false);
        for (int k = 0; k < n; k++) {
            if (j != 0) G0.dat[j][k] = dis[M][k];
            G.dat[j][k] = dis[M][k];
            H.dat[j][k] = dis[m % M][k];
        }
    }

    Matrix R = G0 * G.pow(m / M - 1) * H;
    int ans = INF;
    for (int j = 0; j < n; j++) {
        chmin(ans, R.dat[0][j]);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int ans = solve();
        if (ans >= INF) ans = -1;
        cout << ans << '\n';
    }
    return 0;
}