题解：P9221 「TAOI-1」Pentiment

大弓蛇会平等的创每一个初见 Pentiment byd 的人。

这道题也一样。

首先一眼 dp。

设

f_{i,j}

为当前处于

(i,j)

这个点，且下一步要往上走的方案数。

假定网格周围都是限制点。

令

l_{i,j}

为与

(i,j)

同一行中

(i,j)

左边的第一个限制，同理，

r_{i,j}

为

(i,j)

右边第一个限制。

转移式为

f_{i,j}=\sum^{r_{i,j}-1}_{k=l_{l,r}+1} f_{i-1,k}

因为在这一行中只有

[l_{i,j}+1,r_{i,j}-1]

的点能到达

(i,j)

，所以

f_{i,j}

就是下一步将要走到这些点的方案数之和。

直接 dp 肯定会炸，考虑优化。

对于第

i

行的一个区间

[l,r]

，根据上面的式子，可以得知对于

j\in [l,r]

的所有

(i,j)

，它们的

f_{i,j}

应该是相等的。

然后由于

q

不大，所以很多的

n

个点一定会被分成不多的

f

相同的

q

个区间。

然后做法就多了。

可以用 ODT，动态开点线段树维护当前行的

f

每次用上一行去更新这一行，注意特判连续多行没有限制的情况。

这里给出使用 ODT 的代码。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
const ll mod=998244353;
int n,m,q;
ll ksm(ll a,ll y){
	ll fac=1;
	while(y){
		if(y&1) fac=fac*a%mod;
		a=a*a%mod;
		y>>=1;
	}
	return fac;
}
struct point{
	int x,y;
}a[100005];
bool cmp(point x,point y){
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}
struct node{
	int l,r;
	ll v;
	node(int l_,int r_,ll v_){
		l=l_;
		r=r_;
		v=v_;
	}
	bool operator<(node a)const{
		return l<a.l;
	}
};
set<node>s;
auto split(int x){
	auto t=s.lower_bound(node(x,0,0));
	if(t!=s.end()&&t->l==x) return t;
	t--;
	if(t->r<x) return s.end();
	int l=t->l,r=t->r;
	ll v=t->v;
	s.erase(t);
	s.insert(node(l,x-1,v));
	return s.insert(node(x,r,v)).fi;
}
void dp(int l,int r,bool f){
	if(l>r) return ;
	auto R=split(r+1),L=split(l);
	ll sum=0;
	for(;L!=R;L++){
		sum+=(L->v)*(L->r-L->l+1)%mod;
		sum%=mod;
	}
	R=split(r+1);
	L=split(l);
	s.erase(L,R);
	if(f)s.insert(node(l,r,sum));
	else s.insert(node(l,r,0));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+q,cmp);
	s.insert(node(1,m,1));
	for(int i=1;i<=q;i++){
		int l=i,r=i;
		for(int j=i;j<=q;j++){
			if(a[j].x!=a[i].x){
				break;
			}
			r=j;
		}
		if(a[i-1].x+1<a[i].x){
			ll sum=0;
			for(auto y:s){
				sum+=y.v*(y.r-y.l+1)%mod;
				sum%=mod;
			}
			s.clear();
			s.insert(node(1,m,sum*ksm(m,a[i].x-a[i-1].x-2)%mod));
		}
		for(int j=l;j<=r;j++){
			dp(a[j].y,a[j].y,0);
		}
		dp(1,a[l].y-1,1);
		dp(a[r].y+1,m,1);
		for(int j=l+1;j<=r;j++){
			dp(a[j-1].y+1,a[j].y-1,1);
		}
		i=r;
	}
	ll sum=0;
	for(auto y:s){
		sum+=y.v*(y.r-y.l+1)%mod;
		sum%=mod;
	}
	sum=sum*ksm(m,n-a[q].x)%mod;
	cout<<sum;
	return 0;
}

至此，一锤定音。

尘埃，已然落定。

题解：P9221 「TAOI-1」Pentiment

文章操作

相关推荐

评论

题解：P9221 「TAOI-1」Pentiment