AT_abc388_f Dangerous Sugoroku 题解

太幽默了。

显然可以用矩阵快速幂解决，矩阵里维护距离当前点 \(B\) 以内的所有点可不可达，转移只需分段，在区间内和不在区间内用不同的转移矩阵即可。复杂度 \(O(B^3m\log n)\)。

然后你就 T 了。

此时你很急，你现在应该快点卡常来 AK 这场比赛而不是研究其他的做法，于是我们发现快速幂根本不需要，因为有障碍的区间长度 \(\le B\)，然后没障碍的区间对应的矩阵乘到 \(400\) 次方左右就全大于 \(0\) 了。可以直接预处理出矩阵的幂。

然后 \(A = B\) 时肯定是没有上面那条性质的，需要特判。能走到 \(n\) 的条件显然是 \(n \bmod B \equiv 1\) 且没有障碍 \(\bmod B \equiv 1\)。

然后你就 WA 了。

比赛结束我也没调出来，然后我发现一个重要的事情：

\(B\) 可以等于 \(1\)。

就这样寄了。

代码有点乱。

#include<bits/stdc++.h>
typedef long long ll;
#define pii std::pair<ll,ll>
#define mkp std::make_pair
#define fir first
#define sec second
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
	int ch=getchar();
	T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x*=f;rd(args...);
}
const int N=25;
ll n;int m,A,B;
std::vector<pii> vec;
struct Matrix{
	int m[N][N],n;
	int* operator[](int x){return m[x];}
	Matrix(int _x=0,int _n=B){
		memset(m,0,sizeof m);n=_n;
		for(int i=1;i<=n;i++)m[i][i]=_x;
	}
	Matrix operator*(Matrix b){
		Matrix c=Matrix();
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					(c[i][j]+=m[i][k]*b[k][j]);
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)c[i][j]=(c[i][j]>0);
		}
		return c;
	}
}bas1,bas2,cur,b2[25],b1[405],a1;
signed main(){
	rd(n,m,A,B);
	if(A==B){
		if(B==1)return printf(m?"No":"Yes"),0;
		int flag=(n%B==1ll);
		for(int i=1;i<=m;i++){
			ll l,r;rd(l,r);
			if(r-l+1>=B)flag=0;
			else{
				for(ll j=l;j<=r;j++)if(j%B==1ll)flag=0;
			}
		}
		puts(flag?"Yes":"No");
		return 0;
	}
	ll now=2;
	for(int i=1;i<=m;i++){
		ll l,r;rd(l,r);
		vec.push_back({now,l-1});
		vec.push_back({l,r});
		if(r-l+1>=B){
			puts("No");
			return 0;
		}
		now=r+1;
	}
	vec.push_back({now,n});
	bas1.n=bas2.n=cur.n=B;
	for(int i=2;i<=B;i++)bas2[i][i-1]=bas1[i][i-1]=1;
	for(int i=1;i<=B-A+1;i++)bas1[i][B]=1;
	cur[1][B]=1;
	b2[1]=bas2;b1[1]=bas1;
	for(int i=2;i<=B;i++)b2[i]=b2[i-1]*bas2;
	for(int i=2;i<=400;i++)b1[i]=b1[i-1]*bas1;
	for(int i=1;i<=B;i++){
		for(int j=1;j<=B;j++)a1[i][j]=1;
	}
	int t=0;
	for(auto [l,r]:vec){
		t^=1;
		if(l>r)continue;
		if(t)cur=cur*(r-l+1<=400?b1[r-l+1]:a1);
		else cur=cur*b2[r-l+1];
	}
	printf(cur[1][B]?"Yes":"No");
	return 0;
}