题解：CF2091F Igor and Mountain

· · 题解

简要说明题意：

给出一张 n \times m 的地图，标记为 X 的位置可走。要求从第 n 层的任意位置走到第 1 层的任意位置并满足以下条件：

  1. 每层都必须经过且每层的节点只能经过至多两个。
  2. 如果当前处于 k 层，下一次移动后只能处于 k 层或 k-1 层。
  3. 一次移动的欧式距离 x \leq d。

求路径方案数，对 998244353 取模。

题目分析：

对于点 (i,j)，能到达的同层点为 \{(i,y)| \max\{1,j-d\} \leq y \leq \min\{j+d,m\}\}，能到达 (i,j) 的 i+1 层点应该是 \{(i+1,y)| \max\{1,j-d+1\} \leq y \leq \min\{j+d-1,m\}\}（因为 \lfloor\sqrt{d^2-1}\rfloor \space = \space d-1）。移动的过程可以动态规划，那么考虑一下状态转移方程。

令 f(x,y) 为从第 n 层走到 (x,y) 的方案数，可以得到：

f(x,y)=\sum_{i=\max\{1,y-d\}}^{\min\{y+d,m\}}\sum_{j=\max\{1,i-d+1\}}^{\min\{i+d-1,m\}}f(x+1,j)

看着可能很抽象，其实就是先更新从下层走到本层，再更新本层相互走的情况。

初状态是所有第 n 层可走点赋为 1。

区间求和我用了树状数组，但其实前缀和足够了;D。时间复杂度是 O(nm\log_2m)，前缀和可以把 \log_2m 优化掉，还可以避免调负数取模 WA*2。

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int mod=998244353;
int m;
bool map_[2001][2001];
long long c[2001][2001],f[2001][2001];//这里的c,f都可以滚成两个数组，即当前层和上一层
int lowbit(int v){
    return v&(-v);
}
void modify(long long* c,int x,long long v){
    for(;x<=m;x+=lowbit(x)) (c[x]+=v)%=mod;
}
long long query(long long* c,int l,int r){ //[l,r]
    long long cnt=0ll;
    for(;r;r-=lowbit(r)) cnt+=c[r],cnt%=mod;
    for(--l;l;l-=lowbit(l)) cnt-=c[l],(cnt+=mod)%=mod;
    return cnt%mod;
}
string s;
int main(){
    int T,n,d;
    long long cnt,temp;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&d);
        for(int i=1;i<=n;++i){
            cin>>s,fill(c[i]+1,c[i]+1+m,0ll),fill(f[i]+1,f[i]+1+m,0ll);
            for(int j=0;j<m;++j) map_[i][j+1]=(s[j]=='X');
        }
        for(int i=1;i<=m;++i) f[n][i]=map_[n][i],modify(c[n],i,map_[n][i]);
        for(int i=1;i<=m;++i) if(map_[n][i]) f[n][i]=query(c[n],max(1,i-d),min(m,i+d))%mod;
        for(int i=1;i<=m;++i)
            if(map_[n][i]){
                temp=f[n][i]%mod-query(c[n],i,i),(temp+=mod)%=mod;
                modify(c[n],i,temp);
            }
        for(int i=n-1;i;--i){
            for(int j=1;j<=m;++j)
                if(map_[i][j]){
                    f[i][j]=query(c[i+1],max(1,j-d+1),min(m,j+d-1));
                    // printf("i=%d j=%d f[i][j]=%lld\n",i,j,f[i][j]);
                }
            for(int j=1;j<=m;++j)
                if(map_[i][j]){
                    temp=f[i][j]-query(c[i],j,j),(temp+=mod)%=mod;
                    modify(c[i],j,temp);
                }
            for(int j=1;j<=m;++j) if(map_[i][j]) f[i][j]=query(c[i],max(1,j-d),min(m,j+d));
            for(int j=1;j<=m;++j)
                if(map_[i][j]){
                    temp=f[i][j]-query(c[i],j,j),(temp+=mod)%mod;
                    modify(c[i],j,temp);
                }
        }
        cnt=0ll;
        for(int i=1;i<=m;++i) cnt+=f[1][i],cnt%=mod;
        printf("%lld\n",cnt);
        // for(int i=1;i<=n;putchar('\n'),++i) for(int j=1;j<=m;++j) printf("%lld ",f[i][j]);
    }
    return 0;
}