CF-1013-F. Igor and Mountain（计数类dp） · znzryb
## 思路讲解
感觉是dp，因为是计算路径数量。
首先我们将dp状态定义为到达该点的路径数量（其实也就是同一行之间只能从右往左转移）
然后转移方式如上图所示。
::: 具体转移逻辑（代码）
```cpp
// dp指的是到达该点有多少种路径
for(int i=N;i>=1;--i){
sum[0]=0;
// sum下面一行dp形成的前缀和
for(int j=1;j<=M;++j){
sum[j]=sum[j-1]+dp[i+1][j];
}
sumCur[0]=0;
// sumCur为这一行形成的前缀和
for(int j=1;j<=M;++j){
if(maze[i][j]=='X'){
dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
dp[i][j]%=mod;
sumCur[j]=sumCur[j-1]+dp[i][j];
sumCur[j]%=mod;
}else{
sumCur[j]=sumCur[j-1];
}
}
// #ifdef LOCAL
// cerr<<"sumCur:";
// for(int j=1;j<=M;++j){
// cerr<<sumCur[j]<<" ";
// }
// cerr<<"\n";
// #endif
for(int j=1;j<=M;++j){
if(maze[i][j]=='X'){
// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
dp[i][j]%=mod;
}
}
}
```
:::
## AC代码
::: 源代码
```cpp
// Problem: F. Igor and Mountain
// Contest: Codeforces - Codeforces Round 1013 (Div. 3)
// URL: https://codeforces.com/contest/2091/problem/F
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=998244353;
ll N,M,D,T;
char maze[MAXN][MAXN];
// dpr指的是从右边到达该点有多少种状态
// ll dpr[MAXN][MAXN],dpl[MAXN][MAXN];
ll dp[MAXN][MAXN];
ll sum[MAXN],sumCur[MAXN];
inline void solve(){
cin>>N>>M>>D;
// init
for(int i=0;i<=N+5;++i){
for(int j=0;j<=M+5;++j){
dp[i][j]=0;
}
}
bool haveAns=true;
for(int i=1;i<=N;++i){
bool haveHold=false;
for(int j=1;j<=M;++j){
cin>>maze[i][j];
if(maze[i][j]=='X') haveHold=true;
}
if(!haveHold) haveAns=false;
}
// #ifdef LOCAL
// cerr << "OK1" << '\n';
// #endif
if(!haveAns){
cout<<0<<"\n";
return;
}
for(int i=1;i<=M;++i){
if(maze[N][i]=='X') dp[N][i]=1;
}
// 1^2+?^2=d^2
ll reachDis=sqrtl(D*D-1); // 使用sqrtl保证精度
// #ifdef LOCAL
// cerr << reachDis << '\n';
// #endif
// dp指的是到达该点有多少种路径
for(int i=N;i>=1;--i){
sum[0]=0;
// sum下面一行dp形成的前缀和
for(int j=1;j<=M;++j){
sum[j]=sum[j-1]+dp[i+1][j];
}
sumCur[0]=0;
// sumCur为这一行形成的前缀和
for(int j=1;j<=M;++j){
if(maze[i][j]=='X'){
dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
dp[i][j]%=mod;
sumCur[j]=sumCur[j-1]+dp[i][j];
sumCur[j]%=mod;
}else{
sumCur[j]=sumCur[j-1];
}
}
// #ifdef LOCAL
// cerr<<"sumCur:";
// for(int j=1;j<=M;++j){
// cerr<<sumCur[j]<<" ";
// }
// cerr<<"\n";
// #endif
for(int j=1;j<=M;++j){
if(maze[i][j]=='X'){
// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
dp[i][j]%=mod;
}
}
}
ll ans=0;
for(int i=1;i<=M;++i){
ans+=dp[1][i];
}
ans%=mod;
if(ans<0) ans+=mod;
cout<<ans<<"\n";
// #ifdef LOCAL
// for(int i=1;i<=N;++i){
// for(int j=1;j<=M;++j){
// cerr<<dp[i][j]<<" ";
// }
// cerr<<"\n";
// }
// cerr<<"\n";
// #endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2091/submission/316079969
*/
```
:::
## 心路历程（WA，TLE，MLE……）
这个测试组数7有点问题
[https://codeforces.com/contest/2091/submission/316079483](https://codeforces.com/contest/2091/submission/316079483)
最后发现是没取模，6.