专栏文章

题解：B4401 [蓝桥杯青少年组国赛 2025] 第六题

NNew_Void
B4401题解参与者 8已保存评论 7

文章操作

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

当前评论
7 条
当前快照
1 份
快照标识符
@mio1x3hm
此快照首次捕获于
2025/12/02 12:01
3 个月前
此快照最后确认于
2025/12/02 12:01
3 个月前
查看原文

B4401 [蓝桥杯青少年组国赛 2025] 第六题

题意

给定一个大小为 (h,w)(h,w) 大小的网格，要求出从 (1,1)(1,1) 到 (h,w)(h,w) 的路径中乘积值为 1111 倍数的路径条数，答案对 109+710^9+7 取模。

思路

首先看到这道题，我们不难想到动态规划来解决这道题，但是可以看到数据范围为 10710^7 我们就知道正常的动态规划数组肯定会爆空间，所以我们可以用滚动数组来存储这个行数，那么就很简单了，进行分类讨论：
  • 这条路径的乘积不是 1111 的倍数。
    对于这种情况，由于是乘积，所以我们很好想到，它只能由左边和上边两个路径乘积也不为 1111 的倍数转移过来，所以状态转移就是 dpi,j,0=dpi−1,j,0+dpi,j−1,0dp_{i,j,0}=dp_{i-1,j,0}+dp_{i,j-1,0} 这样，其中第三维的数代表是否是 1111 的倍数。注意到这里只有上一行转移过来，所以可以直接使用滚动数组讲第一维压缩。
  • ai,ja_{i,j} 本身就是 1111 的倍数，那么他的路径乘积就一定是 1111 的倍数，所以可以直接转移过来，转移式子就是 dpi,j,1=dpi,j,0dp_{i,j,1}=dp_{i,j,0} 这样。
  • 这条路径的乘积是 1111 的倍数。
    那么这个点就只能从两个是乘积 1111 倍数的路径转移过来，所以显而易见，状态转移式子就是 dpi,j,1=dpi−1,j,1+dpi,j−1,1dp_{i,j,1}=dp_{i-1,j,1}+dp_{i,j-1,1} 同样可以用滚动数组压缩第一维。
那么这道题就简单的写完了，接下来放出整体代码。

Code

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
const int MOD=1e9+7;
int dp[2][N][2];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    dp[0][1][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int x;
            cin>>x;
            dp[i&1][j][0]=(dp[i&1][j-1][0]+dp[(i-1)&1][j][0])%MOD;
            if (x%11==0) dp[i&1][j][1]=dp[i&1][j][0];
            else dp[i&1][j][1]=(dp[(i-1)&1][j][1]+dp[i&1][j-1][1])%MOD;
        }
    }
    cout<<dp[n&1][m][1]%MOD;
    return 0;
}

评论

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

正在加载评论...