题解：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

。

代码

CPP

#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;
 }

题解：AT_abc388_f [ABC388F] Dangerous Sugoroku

文章操作

思路

代码

相关推荐

评论

题解：AT_abc388_f [ABC388F] Dangerous Sugoroku