题解：AT_abc388_f [ABC388F] Dangerous Sugoroku

· · 题解

思路

赛时想到同余最短路没打出来，就交一发矩乘的题解。

对于每个 [l,r]，显然前后 b-(r-l+1)（相当于 20）个位置是可以暴力转移的，考虑两个区块中间的区域 x 能跳到的是 x+i\ (a \leq i \leq b)。于是一个位置是否可以到达（f_x = 0/1）的转移方程是：

f_x = \bigvee_{j=a}^{\min(b,x-1)} f_{x-j}

可以用矩阵快速幂，时间复杂度是 O(mV^3\log n) 的，于是预处理矩阵 2^k 的状态，时间复杂度 O(mV^2\log n)，V=b-a+1。

代码

#include<bits/stdc++.h>
#define int long long 
#define Mx 25 
using namespace std;
struct mat {
    int a[Mx][Mx];
    mat() {memset(a,0,sizeof a);}
    mat operator*(const mat&x)
    const {
        mat res;
        for(int i=0;i<=20;i++)
            for(int k=0;k<=20;k++) {
                unsigned long long cnt = a[i][k];
                for(int j=0;j<=20;j++) {
                    res.a[i][j] |= (cnt&x.a[k][j]);
                }
            }
        return res;
    }
} fac[45],fac0[45];
struct line {
    int a[Mx];
    line() {memset(a,0,sizeof a);}
    line operator*(const mat&x)
    const {
        line res;
        for(int k=0;k<=20;k++) {
            unsigned long long cnt = a[k];
            for(int j=0;j<=20;j++) {
                res.a[j] |= (cnt&x.a[k][j]);
            }
        }
        return res; 
    }
} S;
void fsp(int x) {
    for(int i=0;i<45;i++)
        if(x&(1ll<<i))S = S*fac[i];
}
void fsp0(int x) {
    for(int i=0;i<45;i++)
        if(x&(1ll<<i))S = S*fac0[i];
}
signed main()
{
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    for(int i=1;i<=19;i++)
        fac[0].a[i+1][i] = fac0[0].a[i+1][i] = 1;
    for(int i=20-b+1;i<=20-a+1;i++)
        fac[0].a[i][20] = 1;
    S.a[20] = 1;
    for(int i=1;i<45;i++)
        fac[i] = fac[i-1]*fac[i-1],
        fac0[i] = fac0[i-1]*fac0[i-1];
    int lst = 1;
    for(int i=1;i<=m;i++) {
        int l,r; cin>>l>>r;
        if(r-l+1 >= 21||l == 1)
            return cout<<"No",0;
        if(l-lst-1 > 0)fsp(l-lst-1);
        if(r-l+1 > 0)fsp0(r-l+1);
        lst = r;
    }
    if(n-lst > 0)fsp(n-lst);
    if(S.a[20])cout<<"Yes";
    else cout<<"No";
    return 0;
 }