题解：CF2145F Long Journey

· · 题解

一种比较暴力的方法。

考虑 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;
}