题解：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 的代码。

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

至此，一锤定音。

尘埃，已然落定。