专栏文章

题解：CF2091F Igor and Mountain

MMagallan_forever
CF2091F题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipt49m2
此快照首次捕获于
2025/12/03 17:30
3 个月前
此快照最后确认于
2025/12/03 17:30
3 个月前
查看原文

简要说明题意：

给出一张 n×mn \times m 的地图，标记为 X 的位置可走。要求从第 nn 层的任意位置走到第 11 层的任意位置并满足以下条件：
  1. 每层都必须经过且每层的节点只能经过至多两个。
  2. 如果当前处于 kk 层，下一次移动后只能处于 kk 层或 k−1k-1 层。
  3. 一次移动的欧式距离 x≤dx \leq d。
求路径方案数，对 998244353998244353 取模。

题目分析：

对于点 (i,j)(i,j)，能到达的同层点为 {(i,y)∣max⁡{1,j−d}≤y≤min⁡{j+d,m}}\{(i,y)| \max\{1,j-d\} \leq y \leq \min\{j+d,m\}\}，能到达 (i,j)(i,j) 的 i+1i+1 层点应该是 {(i+1,y)∣max⁡{1,j−d+1}≤y≤min⁡{j+d−1,m}}\{(i+1,y)| \max\{1,j-d+1\} \leq y \leq \min\{j+d-1,m\}\}（因为 ⌊d2−1⌋ = d−1\lfloor\sqrt{d^2-1}\rfloor \space = \space d-1）。移动的过程可以动态规划，那么考虑一下状态转移方程。
令 f(x,y)f(x,y) 为从第 nn 层走到 (x,y)(x,y) 的方案数，可以得到：
f(x,y)=∑i=max⁡{1,y−d}min⁡{y+d,m}∑j=max⁡{1,i−d+1}min⁡{i+d−1,m}f(x+1,j)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)
看着可能很抽象，其实就是先更新从下层走到本层，再更新本层相互走的情况。
初状态是所有第 nn 层可走点赋为 11。
区间求和我用了树状数组，但其实前缀和足够了;D。时间复杂度是 O(nmlog⁡2m)O(nm\log_2m)，前缀和可以把 log⁡2m\log_2m 优化掉，还可以避免调负数取模 WA*2。
代码如下：
CPP
#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;
}

评论

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

正在加载评论...