打卡信奥刷题（3375）用C++实现信奥题 P9759 [COCI 2022/2023 #3] Bomboni

P9759 [COCI 2022/2023 #3] Bomboni

题目描述

Iva 是一个狂热的糖果迷！在她面前是一块填满糖果和障碍的 $n\times n$ 的土地。Iva 目前在左上角。通过向右或向下移动，她要前往右下角。Iva 目前所在的格子没有障碍。

在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知道一共有多少条这样的路径。由于答案可能很大，她只想知道答案模 $998244353$ 的结果。

输入格式

第一行两个整数 $n,k$，表示土地的边长和 Iva 的最喜欢的数字。

在接下来的 $n$ 行中，每一行 $n$ 个数字，描述这片土地。如果 $a_{i,j}=-1$，那么这块土地就是障碍物，否则满足这块土地包含一个 $1\le a_{i,j}\le 10^6$ 的数。

输出格式

一行一个整数表示结果。

输入输出样例 #1

输入 #1

2 2
3 2
1 4

输出 #1

2

输入输出样例 #2

输入 #2

3 6
5 2 -1
7 3 6
-1 3 1

输出 #2

3

说明/提示

【样例解释 #2】

共有三条这样的路线：

• 5-2-3-3-1
• 5-2-3-6-1
• 5-7-3-6-1

【数据范围】

对于 $100\%$ 的数据，满足 $1\le n\le 500,1\le k\le 10^6,-1\le a_{i,j}\le 10^6$。

本题满分 $110$ 分。

C++实现

#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll N=510,mod=998244353;
unordered_map<ll,ll>f[N][N];
ll n,k,a[N][N];
ll gcd(ll u,ll v){
if(u%v) return gcd(v,u%v);
return v;
}
int main(){
cin>>n>>k;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==–1) continue;
if(i==1&&j==1){
f[1][1][gcd(a[i][j],k)]=1;
continue;
}
if(a[i–1][j]!=–1){
for(auto m:f[i–1][j]){
ll num=gcd(k,m.first*a[i][j]);
f[i][j][num]+=m.second,f[i][j][num]%=mod;
}
}
if(a[i][j–1]!=–1){
for(auto m:f[i][j–1]){
ll num=gcd(k,m.first*a[i][j]);
f[i][j][num]+=m.second,f[i][j][num]%=mod;
}
}
}
}
cout<<f[n][n][k];
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容