网站域名打不开,企业官方网站的作用,郑州网站建设技术方案,谷歌外贸seo文章目录 题目题目描述输入输出格式数据范围测试样例 思路代码复杂度分析时间复杂度空间复杂度 题目
题目链接#x1f517;
题目描述 如图所示#xff0c;爱丽丝在一个3x3的迷宫之中#xff0c;每个方格中标有 1 − 9 1-9 1−9各不相同的数字#xff0c;爱丽丝可以从一格… 文章目录 题目题目描述输入输出格式数据范围测试样例 思路代码复杂度分析时间复杂度空间复杂度 题目
题目链接
题目描述 如图所示爱丽丝在一个3x3的迷宫之中每个方格中标有 1 − 9 1-9 1−9各不相同的数字爱丽丝可以从一格出发到达任意相邻的格子。每到达一个格子爱丽丝便获得了该格子上的数字假设爱丽丝以 1 → 3 → 5 1\to3\to5 1→3→5 的顺序走过格子她就获得了 135长度为3的字符串。爱丽丝可能从任意一格出发请你计算长度为 n n n 的字符串一共有多少种可能性。答案可能很大最终答案请对 998244353 998244353 998244353 取模。 注不完全相同的两个字符串为两种不同的可能性如 135 和 139 135 和 131。 同一格子可以重复走过。
输入输出格式
【输入格式】
共 4 4 4 行 第 1 1 1行到第 3 3 3行每行 3 3 3个用空格分隔开的数字 a i j ( 1 ≤ a i j ≤ 9 ) a_{ij} (1 \le a_{ij} \le 9) aij(1≤aij≤9)代表第 i i i行第 j j j列格子上的数字。
第 4 4 4行输入一个数字 n n n表示字符串的长度。
【输出格式】
共 1 1 1 行 输出长度为 n n n 的字符串的所有可能性对 998244353 998244353 998244353 的模数。
数据范围 1 ≤ a i j ≤ 9 1 \le a_{ij} \le 9 1≤aij≤9 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105
测试样例
input1
1 2 3
4 5 6
7 8 9
2output1:
24input2:
3 2 1
9 8 7
4 5 6
100000output2:
528035646思路
题目给定了9个数字之间相互不一样则具体是什么数字已经不重要了题目化简为具体来说给定一个 3x3 的迷宫每个格子都可以作为起点爱丽丝可以从一个格子出发按照某种规则在相邻格子中移动经过 n 步后最终到达其他格子。计算所有这样的路径的数量并输出结果。 我们可以用一个三维数组用来存储从某个位置 (x, y) 出发经过 n 步后可以到达的路径数量。结果需要对这个质数取模。 计算的过程中可以使用深度优先搜索递归计算从迷宫中的某个格子出发经过 n 步后能到达的所有路径的数量由于数据量较大可以采用记忆化搜索来避免重复计算从而提高效率。 递归思路如下 递归定义 函数 dfs(x, y, n) 计算从 (x, y) 这个位置出发经过 n 步可以达到的所有可能路径的数量。递归边界条件 当 n 1 时表示路径的长度为 1起点本身就是一个有效路径。因此dfs(x, y, 1) 直接返回 1表示当前位置的路径数量为 1。递归转移 对于每个 (x, y) 格子函数会检查该格子周围的 8 个相邻格子上下左右以及四个对角线方向的格子。对于每一个相邻格子 (i, j)如果它与当前位置 (x, y) 相邻即 abs(i-x) abs(j-y) 1那么递归地调用 dfs(i, j, n-1) 来计算从该相邻格子出发经过 n-1 步能到达的路径数量。 然后将所有这些相邻格子的结果加起来得到当前位置 (x, y) 出发经过 n 步的路径总数。记忆化搜索 mem[x][y][n] 用来记录已经计算过的结果避免重复计算。如果 mem[x][y][n] 不为 0表示该状态已经计算过直接返回该结果。这大大提高了效率因为同一个状态从某个位置出发经过相同步数不会被重复计算。递归的返回值 每次递归的结果是将相邻格子通过递归计算得到的路径数量进行累加并对 998244353 取模以确保结果不会超过整数范围。 代码
#includebits/stdc.h
using namespace std;
using lllong long;
using ldlong double;
constexpr int p998244353;ll mem[5][5][100005];
ll dfs(int x, int y, int n)
{if(mem[x][y][n]!0)return mem[x][y][n];if(n1)return mem[x][y][n]1;ll res0;for(int i1;i3;i)for(int j1;j3;j)if(abs(i-x)abs(j-y)1)res (res dfs(i, j, n-1)) % p;return mem[x][y][n] res;
}int main()
{int n;for(int i0;i9;i)cinn;ll ans0;for(int i1;i3;i)for(int j1;j3;j)ans(ansdfs(i,j,n))%p;coutans;return 0;
}复杂度分析
时间复杂度 递归调用 递归函数 d f s ( x , y , n ) dfs(x, y, n) dfs(x,y,n) 的目的是计算从位置 ( x , y ) (x, y) (x,y) 出发经过 n n n 步能够到达的所有路径数量。对于每个位置 ( x , y ) (x, y) (x,y)递归需要访问它的相邻格子最多有 4 4 4 个相邻格子并进行递归调用。 因此每次递归都会对最多 4 4 4 个相邻格子进行递归调用。 记忆化搜索 通过记忆化数组 m e m [ x ] [ y ] [ n ] mem[x][y][n] mem[x][y][n] 来避免重复计算如果某个 ( x , y , n ) (x, y, n) (x,y,n) 状态已经计算过直接返回已存储的结果。这意味着每个状态只会计算一次从而避免了指数级的重复计算。 递归的状态数 递归的状态由 $(x, y) $和 n n n 决定。由于迷宫的大小是固定的 3 ∗ 3 3*3 3∗3因此有 9 个可能的 ( x , y ) (x, y) (x,y) 位置。 对于每个位置 n n n 可以从 1 1 1 到给定的最大步数 n n n 进行递归。因此递归的状态数为 状态数 9 × n 状态数9×n 状态数9×n其中 9 9 9 是 ( x , y ) (x, y) (x,y) 的取值范围 n n n 是步数的最大值。 每次递归的工作量 每次递归需要遍历最多 4 4 4 个相邻格子并对每个相邻格子进行递归调用。这部分的计算量是常数级别的 O ( 1 ) O(1) O(1)。 综上时间复杂度可以表示为 时间复杂度 O ( 9 × n 4 ) O ( 36 n ) 时间复杂度O(9×n4)O(36n) 时间复杂度O(9×n4)O(36n) 由于常数项 36 36 36 可以忽略不计最终的时间复杂度为 O ( n ) O(n) O(n)
空间复杂度
记忆化数组 记忆化数组 m e m [ x ] [ y ] [ n ] mem[x][y][n] mem[x][y][n] 用于存储每个位置 ( x , y ) (x, y) (x,y) 和步数 n n n 的计算结果。因为 ( x , y ) (x, y) (x,y) 的位置有 9 9 9 个而步数 n n n 最大为给定的 n n n所以数组的大小为 m e m 数组的大小 9 × n mem 数组的大小9×n mem数组的大小9×n递归栈空间 递归的最大深度为 n n n因为递归每次调用时步数 n n n 减 1 1 1。因此递归栈的空间复杂度为 O ( n ) O(n) O(n)。
综上空间复杂度为 空间复杂度 O ( 9 × n n ) O ( n ) 空间复杂度O(9×nn)O(n) 空间复杂度O(9×nn)O(n)
