专栏文章

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

FFS_NEO
AT_arc190_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6ihrz
此快照首次捕获于
2025/12/01 21:22
3 个月前
此快照最后确认于
2025/12/01 21:22
3 个月前
查看原文
暴力 DP 是平凡的，我们思考如何处理修改操作。
设 fi,jf_{i,j} 为从 (1,1)(1,1) 走到 (i,j)(i,j) 的不包括点 (i,j)(i,j) 的权值和，gi,jg_{i,j} 为从 (n,m)(n,m) 走到 (i,j)(i,j) 的不包括点 (i,j)(i,j) 的权值和。于是修改一个点对答案的影响就是 Ai,j′×fi,j′×gi,j′−Ai,j×fi,j×gi,jA'_{i,j} \times f'_{i,j} \times g'_{i,j} - A_{i,j} \times f_{i,j} \times g_{i,j}。每次单点改影响的 f,gf,g 矩阵很大，但是修改点都是相邻的，于是我们只要修改一行或列即可，这样下次修改时用的前置状态一定更新过。
CPP
/*

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...