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

New_Void · 2025-08-31 03:04:33 · 题解

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

题意

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

思路

首先看到这道题，我们不难想到动态规划来解决这道题，但是可以看到数据范围为 10^7 我们就知道正常的动态规划数组肯定会爆空间，所以我们可以用滚动数组来存储这个行数，那么就很简单了，进行分类讨论：

• 这条路径的乘积不是 11 的倍数。

  对于这种情况，由于是乘积，所以我们很好想到，它只能由左边和上边两个路径乘积也不为 11 的倍数转移过来，所以状态转移就是 dp_{i,j,0}=dp_{i-1,j,0}+dp_{i,j-1,0} 这样，其中第三维的数代表是否是 11 的倍数。注意到这里只有上一行转移过来，所以可以直接使用滚动数组讲第一维压缩。

• 这条路径的乘积是 11 的倍数。

  那么这个点就只能从两个是乘积 11 倍数的路径转移过来，所以显而易见，状态转移式子就是 dp_{i,j,1}=dp_{i-1,j,1}+dp_{i,j-1,1} 同样可以用滚动数组压缩第一维。

那么这道题就简单的写完了，接下来放出整体代码。

Code

#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;
}