题解：AT_arc190_c [ARC190C] Basic Grid Problem with Updates

· · 题解

暴力 DP 是平凡的，我们思考如何处理修改操作。

设 f_{i,j} 为从 (1,1) 走到 (i,j) 的不包括点 (i,j) 的权值和，g_{i,j} 为从 (n,m) 走到 (i,j) 的不包括点 (i,j) 的权值和。于是修改一个点对答案的影响就是 A'_{i,j} \times f'_{i,j} \times g'_{i,j} - A_{i,j} \times f_{i,j} \times g_{i,j}。每次单点改影响的 f,g 矩阵很大，但是修改点都是相邻的，于是我们只要修改一行或列即可，这样下次修改时用的前置状态一定更新过。

/*

        2025.11.17

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=200005,mod=998244353;
int n,m,Q,X,Y,ans;
vector<int>f[MAXN],g[MAXN],a[MAXN];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n+1;i++)f[i].assign(m+5,0),g[i].assign(m+5,0),a[i].assign(m+5,0);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
    f[1][1]=1,g[n][m]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(i!=1||j!=1)f[i][j]=(f[i-1][j]*a[i-1][j]+f[i][j-1]*a[i][j-1])%mod;
    for(int i=n;i>=1;i--)for(int j=m;j>=1;j--)if(i!=n||j!=m)g[i][j]=(g[i+1][j]*a[i+1][j]+g[i][j+1]*a[i][j+1])%mod;
    ans=a[n][m]*f[n][m]%mod;
    cin>>Q>>X>>Y;
    while(Q--){
        char t;int x;
        cin>>t>>x;
        if(t=='L')Y--;
        if(t=='R')Y++;
        if(t=='U')X--;
        if(t=='D')X++;
        if(n<m){
            for(int i=1;i<=n;i++)if(i!=1||Y!=1)f[i][Y]=(f[i-1][Y]*a[i-1][Y]+f[i][Y-1]*a[i][Y-1])%mod;
            for(int i=n;i>=1;i--)if(i!=n||Y!=m)g[i][Y]=(g[i+1][Y]*a[i+1][Y]+g[i][Y+1]*a[i][Y+1])%mod;
        }
        else{
            for(int i=1;i<=m;i++)if(X!=1||i!=1)f[X][i]=(f[X-1][i]*a[X-1][i]+f[X][i-1]*a[X][i-1])%mod;
            for(int i=m;i>=1;i--)if(X!=n||i!=m)g[X][i]=(g[X+1][i]*a[X+1][i]+g[X][i+1]*a[X][i+1])%mod;
        }
        ans-=f[X][Y]*g[X][Y]%mod*a[X][Y]%mod;
        a[X][Y]=x;
        if(n<m){
            for(int i=1;i<=n;i++)if(i!=1||Y!=1)f[i][Y]=(f[i-1][Y]*a[i-1][Y]+f[i][Y-1]*a[i][Y-1])%mod;
            for(int i=n;i>=1;i--)if(i!=n||Y!=m)g[i][Y]=(g[i+1][Y]*a[i+1][Y]+g[i][Y+1]*a[i][Y+1])%mod;
        }
        else{
            for(int i=1;i<=m;i++)if(X!=1||i!=1)f[X][i]=(f[X-1][i]*a[X-1][i]+f[X][i-1]*a[X][i-1])%mod;
            for(int i=m;i>=1;i--)if(X!=n||i!=m)g[X][i]=(g[X+1][i]*a[X+1][i]+g[X][i+1]*a[X][i+1])%mod;
        }
        ans=((ans+f[X][Y]*g[X][Y]%mod*a[X][Y]%mod)%mod+mod)%mod;
        cout<<ans<<'\n';
    }
    return 0;
}