Codeforces Round 1013 (Div. 3)-F

 Go to the problem

题目大意及样例：

 思路：从第n层到第1层倒着转移，dp[i][j][1]表示第i+1层点到(i,j)的路线方案（只存从下面的点转移过来的贡献）,dp[i][j][2]表示从本层点和上一层点（即i+1层）到（i,j）的路线方案，为什么要单独维护一个从i+1层的点转移过来的方案呢？因为只有更新完，本层每个点，只考虑从i+1的点转移过来的路线方案，才能加上本层点过来的这份贡献（不然本层点的贡献就是0了），然后能产生贡献的点必然是在某个区间内，所以还要维护这俩个dp的前缀和，用pre[i][j][1/2]分别表示，具体的转移可以看下面代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2010;
char s[N][N];
int dp[N][N][3];
int pre[N][N][3];
int mod=998244353;
void solve(){int n,m,d;cin>>n>>m>>d;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>s[i][j];dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;pre[i][j][0]=pre[i][j][1]=pre[i][j][2]=0;}}//对第n初始化for(int j=1;j<=m;j++){//   pre[n][j][1]=pre[n][j-1][1];if(s[n][j]=='X'){//    pre[n][j][1]++;dp[n][j][1]=1;}pre[n][j][1]=(pre[n][j-1][1]+dp[n][j][1])%mod;}//然后是dp[n][1-m][2]的初始化for(int j=1;j<=m;j++){int l=max(1ll,j-d),r=min(j+d,m);if(s[n][j]=='X') dp[n][j][2]=((pre[n][r][1]-pre[n][l-1][1])%mod+mod)%mod;pre[n][j][2]=(pre[n][j-1][2]+dp[n][j][2])%mod;}for(int i=n-1;i>=1;i--){for(int j=1;j<=m;j++){if(s[i][j]=='X'){int lk=(int)sqrt(d*d-1);int l=max(1ll,j-lk),r=min(m,j+lk);dp[i][j][1]=((pre[i+1][r][2]-pre[i+1][l-1][2])%mod+mod)%mod;}pre[i][j][1]=(pre[i][j-1][1]+dp[i][j][1])%mod;}for(int j=1;j<=m;j++){int l=max(1ll,j-d),r=min(m,j+d);if(s[i][j]=='X') dp[i][j][2]=((pre[i][r][1]-pre[i][l-1][1])%mod+mod)%mod;pre[i][j][2]=(pre[i][j-1][2]+dp[i][j][2])%mod;}}// for(int i=n;i>=1;i--){//   for(int j=1;j<=m;j++){//       cout<<i<<' '<<j<<'\n';//       cout<<dp[i][j][1]<<' '<<dp[i][j][2]<<'\n';//   }// }cout<<pre[1][m][2]%mod<<'\n';
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--) solve();return 0;
}

2025/3/29 Update:修正了注释和几处笔误。