一種比較暴力的方法。

考慮 \(n\le10,a_i\le10\) 所以陷阱的狀態僅 \(n\) 種，而且每 \(\operatorname{lcm}(a_0,a_1,...,a_{n-1})\) 個格子就是一個陷阱狀態的周期，我們不妨記 \(l=\operatorname{lcm}(a_0,a_1,...,a_{n-1})\)，我們可以先求出時間 \(t\bmod n=0,1,...,n-1\) 時向后走 0 到 \(l\) 格需要的最短時間，這很明顯可以用 bitset 求，先處理出 \(a_{i,j},i\in[0,n-1]\ j\in[0,l]\) 表示在時間 \(t\bmod n=i\) 時第 \(j\) 格的狀態，1 表示無陷阱，反之 0 表示有陷阱，然后將 \(b\) 先設置為 1 表示 0 現在是可以到達的，對于向后走一步那么就是 \(b<<1\)，停留就是 \(b\) 本身，于是在時間 \(t\) 時向后走一步或停留的狀態就是 \([(b<<1)|b]\&a_{t\bmod n}\)，很明顯走到第 \(i\) 格的最短時間是必然大于走到第 \(i-1\) 格的最短時間的，所以我們可以維護一個指針不斷判斷 \(b_i\) 是否等于 1 來求 \(dis_{i,j}\)， 其中 \(i\) 表示起始時間 \(t\bmod n\)，\(j\) 表示走到第 \(j\) 格。由于 \(m\le 10^{12}\)，所以我們可以考慮倍增的方法跳 \(\lfloor\frac{m}{l}\rfloor\) 個 \(l\) 格，然后使用 \(dis\) 數組求余下的 \(m\bmod l\) 格的最短時間。

但考慮一個問題，上面的寫法是在可以到達的條件下的，我們可以將 \(dis_{i,j},j\in[1,l]\) 賦值為一個極大值 \(inf\)，在計算 \(b\) 時將最大轉移次數設置為 \(k\cdot l\)，如果最后計算出的最短時間 \(t\geq inf\)，即認為是無法到達的。最后時間復雜度是 \(O(\frac{Tnkl^2}{\omega}+Tn\log m)\)，當 \(k=6\) 時既可以保證正確性，也可以保證時間不超時。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,a[15],b[15],len,dis[15][2600],power[50];
__int128 f[15][45];
bitset<2600> c,d[15],e[15];
signed main(){
    power[0]=1;
    for(int i=1;i<=41;i++)power[i]=power[i-1]*2;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++) fill(dis[i],dis[i]+2550,1e14);
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        len=a[0];
        for(int i=1;i<n;i++) len=lcm(len,a[i]);
        for(int i=0;i<n;i++){e[i].set();for(int j=b[i];j<=len;j+=a[i])e[i].reset(j);}
        for(int i=0;i<n;i++){
            c.set(0);
            dis[i][0]=0;
            int id=1;
            for(int j=0;j<6*len&&id<=len;j++){
                c=((c<<1)|c)&e[(i+j)%n];
                if(c[id])dis[i][id++]=j+1;
            }
            f[i][0]=dis[i][len];
        }
        int l=1,k=floor(m/len);
        for(int i=1;i<=41&&l<=k;i++){for(int j=0;j<n;j++)f[j][i]=f[j][i-1]+f[(j+f[j][i-1])%n][i-1];l<<=1;}
        __int128 tot=0;
        for(int i=41;i>=0;i--)if(k>=power[i]){tot+=f[tot%n][i];k-=1ll*power[i];}
        tot+=dis[tot%n][m%len];
        if(tot>=1e14) {cout<<-1<<endl;continue;}
        else cout<<(int)tot<<endl;
    }
    return 0;
}