专栏文章

题解：CF2145F Long Journey

ccogimyun
CF2145F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink2sfn
此快照首次捕获于
2025/12/02 03:42
3 个月前
此快照最后确认于
2025/12/02 03:42
3 个月前
查看原文
一种比较暴力的方法。
考虑 n≤10,ai≤10n\le10,a_i\le10 所以陷阱的状态仅 nn 种，而且每 lcm⁡(a0,a1,...,an−1)\operatorname{lcm}(a_0,a_1,...,a_{n-1}) 个格子就是一个陷阱状态的周期，我们不妨记 l=lcm⁡(a0,a1,...,an−1)l=\operatorname{lcm}(a_0,a_1,...,a_{n-1})，我们可以先求出时间 t mod n=0,1,...,n−1t\bmod n=0,1,...,n-1 时向后走 0 到 ll 格需要的最短时间，这很明显可以用 bitset 求，先处理出 ai,j,i∈[0,n−1] j∈[0,l]a_{i,j},i\in[0,n-1]\ j\in[0,l] 表示在时间 t mod n=it\bmod n=i 时第 jj 格的状态，1 表示无陷阱，反之 0 表示有陷阱，然后将 bb 先设置为 1 表示 0 现在是可以到达的，对于向后走一步那么就是 b<<1b<<1，停留就是 bb 本身，于是在时间 tt 时向后走一步或停留的状态就是 [(b<<1)∣b]&at mod n[(b<<1)|b]\&a_{t\bmod n}，很明显走到第 ii 格的最短时间是必然大于走到第 i−1i-1 格的最短时间的，所以我们可以维护一个指针不断判断 bib_i 是否等于 1 来求 disi,jdis_{i,j}， 其中 ii 表示起始时间 t mod nt\bmod n，jj 表示走到第 jj 格。由于 m≤1012m\le 10^{12}，所以我们可以考虑倍增的方法跳 ⌊ml⌋\lfloor\frac{m}{l}\rfloor 个 ll 格，然后使用 disdis 数组求余下的 m mod lm\bmod l 格的最短时间。
但考虑一个问题，上面的写法是在可以到达的条件下的，我们可以将 disi,j,j∈[1,l]dis_{i,j},j\in[1,l] 赋值为一个极大值 infinf，在计算 bb 时将最大转移次数设置为 k⋅lk\cdot l，如果最后计算出的最短时间 t≥inft\geq inf，即认为是无法到达的。最后时间复杂度是 O(Tnkl2ω+Tnlog⁡m)O(\frac{Tnkl^2}{\omega}+Tn\log m)，当 k=6k=6 时既可以保证正确性，也可以保证时间不超时。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...