题解：CF2145F Long Journey

· · 题解

记 V={\rm lcm}\{2,3,\cdots,10\}=2520。

记 f_{i,S} 表示在一个 \bmod\ n=i 的时刻结束时到达 \bmod\ {\rm lcm}=S 的最小等待时间。可以直接建一张大小为 nV 的图出来跑 bfs。

这样，我们把 [0,m] 的路径分成若干个大小为 V 的块。我们发现通过一整块的时间仍然与到达块首的位置有关。所以再定义状态 g_{i,j} 表示钦定在一个 \bmod\ n=i 的时刻结束时到达块首，在一个 \bmod\ n=j 的时刻结束时到达块尾所需要花的最小时间，这其实是一个矩阵转移的形式，转移系数可以直接通过跑 n 次 bfs 来获得。

矩阵快速幂即可。剩下的余块可以直接查表，复杂度 O(t(n^2V+n^3\log m))。

代码里写的是 dijkstra。

::::success[Code]

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

typedef long long ll;
#define INF (ll)1e18

const int N = 10;
const int V = 2520;

int n,a[N],b[N],vis[N][V + 1];
ll dis[N][N][V + 1],m;

struct node{
    int ti,pos; ll dis;
    inline bool operator <( const node &b ) const{
        return b.dis < dis;
    }
};

inline bool judge( int tim , int S ){ return S % a[tim] != b[tim]; }

vector< pair<int,int> > E[10][V + 1];

priority_queue<node> Q;

inline void dijkstra( int st ){
    for( int i = 0 ; i < n ; i ++ )
        for( int j = 0 ; j <= V ; j ++ ) dis[st][i][j] = INF,vis[i][j] = 0;
    dis[st][st][0] = 0; Q.push( node{ st , 0 , 0 } );
    while( !Q.empty() ){
        node u = Q.top(); Q.pop();
        if( vis[u.ti][u.pos] ) continue;
        vis[u.ti][u.pos] = 1;
        for( pair<int,int> v : E[u.ti][u.pos] ){
            if( dis[st][v.first][v.second] > u.dis + 1 ){
                dis[st][v.first][v.second] = u.dis + 1;
                if( !vis[v.first][v.second] ) Q.push( node{ v.first , v.second , dis[st][v.first][v.second] } );
            }
        }
    }
}

inline void clear(){
    for( int i = 0 ; i < n ; i ++ ) a[i] = b[i] = 0;
    for( int st = 0 ; st < n ; st ++ )
        for( int i = 0 ; i < n ; i ++ )
            for( int j = 0 ; j <= V ; j ++ ) vis[i][j] = dis[st][i][j] = 0,E[i][j].clear();
}

struct matrix{
    ll a[N][N];
    matrix(){
        for( int i = 0 ; i < N ; i ++ )
            for( int j = 0 ; j < N ; j ++ ) a[i][j] = INF;
    }
    inline void build(){
        for( int i = 0 ; i < N ; i ++ )
            for( int j = 0 ; j < N ; j ++ ) a[i][j] = ( i == j ) ? 0 : INF;
    }
    inline matrix operator *( matrix B ){
        matrix C;
        for( int i = 0 ; i < N ; i ++ )
            for( int j = 0 ; j < N ; j ++ )
                for( int k = 0 ; k < N ; k ++ )
                    C.a[i][j] = min( C.a[i][j] , a[i][k] + B.a[k][j] );
        return C;
    }
};

inline matrix fp( matrix A , ll p ){
    matrix res; res.build();
    while( p ){
        if( p & 1 ) res = res * A;
        A = A * A;
        p >>= 1;
    }
    return res;
}

inline void solve(){
    scanf("%d%lld",&n,&m);
    for( int i = 1 ; i < n ; i ++ ) scanf("%d",&a[i]); scanf("%d",&a[0]);
    for( int i = 1 ; i < n ; i ++ ) scanf("%d",&b[i]); scanf("%d",&b[0]);
    for( int i = 0 ; i < n ; i ++ ){
        for( int j = 0 ; j < V ; j ++ ){
            int nxt = ( i + 1 ) % n;
            if( judge( nxt , j + 1 ) ) E[i][j].emplace_back( make_pair( nxt , j + 1 ) );
            if( judge( nxt , j ) ) E[i][j].emplace_back( make_pair( nxt , j ) );
        }
    }
    for( int i = 0 ; i < n ; i ++ ) dijkstra( i );
    matrix R,F;
    for( int i = 0 ; i < n ; i ++ )
        for( int j = 0 ; j < n ; j ++ ) R.a[i][j] = dis[i][j][V];
    for( int i = 1 ; i < n ; i ++ ) F.a[0][i] = INF; F.a[0][0] = 0;
    F = F * fp( R , m / V );
    ll Ans = INF;
    for( int i = 0 ; i < n ; i ++ )
        for( int j = 0 ; j < n ; j ++ ) Ans = min( Ans , F.a[0][i] + dis[i][j][m % V] );
    if( Ans == INF ) Ans = -1;
    printf("%lld\n",Ans);
    clear();
}

signed main(){
    int testcase; scanf("%d",&testcase);
    while( testcase -- ) solve();
    return 0;
}

::::