【QED】爱丽丝与混沌的无尽海

题目

题目链接🔗

题目描述

如图所示，爱丽丝在一个3x3的迷宫之中，每个方格中标有$1-9$各不相同的数字，爱丽丝可以从一格出发，到达任意相邻的格子。每到达一个格子，爱丽丝便获得了该格子上的数字，假设爱丽丝以 $1\to 3\to 5$ 的顺序走过格子，她就获得了 135，长度为3的字符串。爱丽丝可能从任意一格出发，请你计算长度为 $n$ 的字符串一共有多少种可能性。答案可能很大，最终答案请对 $998244353$ 取模。
注：不完全相同的两个字符串为两种不同的可能性，如 135 和 139 ，135 和 131。
同一格子可以重复走过。

输入输出格式

【输入格式】

共 $4$ 行
第$1$行到第$3$行，每行$3$个用空格分隔开的数字$a_{ij}(1\le a_{ij}\le 9)$，代表第$i$行第$j$列格子上的数字。

第$4$行输入一个数字 $n$，表示字符串的长度。

【输出格式】

共 $1$ 行
输出长度为 $n$ 的字符串的所有可能性对 $998244353$ 的模数。

数据范围

$1\le a_{ij}\le 9$
$1\le n\le 10^5$

测试样例

input1：

1 2 3
4 5 6
7 8 9
2

output1:

24

input2:

3 2 1
9 8 7
4 5 6
100000

output2:

528035646

思路

题目给定了9个数字之间相互不一样，则具体是什么数字已经不重要了，题目化简为：具体来说，给定一个 3x3 的迷宫，每个格子都可以作为起点，爱丽丝可以从一个格子出发，按照某种规则在相邻格子中移动，经过 n 步后最终到达其他格子。计算所有这样的路径的数量，并输出结果。
我们可以用一个三维数组，用来存储从某个位置 (x, y) 出发，经过 n 步后可以到达的路径数量。结果需要对这个质数取模。
计算的过程中可以使用深度优先搜索递归计算从迷宫中的某个格子出发，经过 n 步后能到达的所有路径的数量，由于数据量较大，可以采用记忆化搜索来避免重复计算，从而提高效率。
递归思路如下：

1. 递归定义：
   函数 dfs(x, y, n) 计算从 (x, y) 这个位置出发，经过 n 步可以达到的所有可能路径的数量。
2. 递归边界条件：
   当 n == 1 时，表示路径的长度为 1，起点本身就是一个有效路径。因此，dfs(x, y, 1) 直接返回 1，表示当前位置的路径数量为 1。
3. 递归转移：
   对于每个 (x, y) 格子，函数会检查该格子周围的 8 个相邻格子（上下左右以及四个对角线方向的格子）。对于每一个相邻格子 (i, j)，如果它与当前位置 (x, y) 相邻，即 abs(i-x) + abs(j-y) == 1，那么递归地调用 dfs(i, j, n-1) 来计算从该相邻格子出发，经过 n-1 步能到达的路径数量。
   然后将所有这些相邻格子的结果加起来，得到当前位置 (x, y) 出发，经过 n 步的路径总数。
4. 记忆化搜索：
   mem[x][y][n] 用来记录已经计算过的结果，避免重复计算。如果 mem[x][y][n] 不为 0，表示该状态已经计算过，直接返回该结果。这大大提高了效率，因为同一个状态（从某个位置出发，经过相同步数）不会被重复计算。
5. 递归的返回值：
   每次递归的结果是将相邻格子通过递归计算得到的路径数量进行累加，并对 998244353 取模，以确保结果不会超过整数范围。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
constexpr int p=998244353;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(n==1)return mem[x][y][n]=1;ll res=0;for(int i=1;i<=3;i++)for(int j=1;j<=3;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 i=0;i<=9;i++)cin>>n;ll ans=0;for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)ans=(ans+dfs(i,j,n))%p;cout<<ans;return 0;
}

复杂度分析

时间复杂度

1. 递归调用：
   递归函数 $dfs(x,y,n)$ 的目的是计算从位置 $(x,y)$ 出发，经过 $n$ 步能够到达的所有路径数量。对于每个位置$(x,y)$，递归需要访问它的相邻格子（最多有 $4$ 个相邻格子），并进行递归调用。
   因此，每次递归都会对最多 $4$ 个相邻格子进行递归调用。

2. 记忆化搜索：
   通过记忆化数组 $mem[x][y][n]$ 来避免重复计算，如果某个 $(x,y,n)$ 状态已经计算过，直接返回已存储的结果。这意味着每个状态只会计算一次，从而避免了指数级的重复计算。

3. 递归的状态数：
   递归的状态由 $(x, y) $和 $n$ 决定。由于迷宫的大小是固定的$（3\ast 3）$，因此有 9 个可能的 $(x,y)$ 位置。
   对于每个位置，$n$ 可以从 $1$ 到给定的最大步数 $n$ 进行递归。因此，递归的状态数为：
   $$状态数=9\times n$$其中，$9$ 是 $(x,y)$ 的取值范围，$n$ 是步数的最大值。

4. 每次递归的工作量：
   每次递归需要遍历最多 $4$ 个相邻格子，并对每个相邻格子进行递归调用。这部分的计算量是常数级别的 $O(1)$。
   综上，时间复杂度可以表示为：

$$时间复杂度=O(9\times n4)=O(36n)$$
由于常数项 $36$ 可以忽略不计，最终的时间复杂度为：
$$O(n)$$

空间复杂度

1. 记忆化数组：
   记忆化数组 $mem[x][y][n]$ 用于存储每个位置 $(x,y)$ 和步数 $n$ 的计算结果。因为 $(x,y)$ 的位置有 $9$ 个，而步数 $n$ 最大为给定的 $n$，所以数组的大小为：
   $$mem数组的大小=9\times n$$
2. 递归栈空间：
   递归的最大深度为 $n$（因为递归每次调用时，步数 $n$ 减 $1$）。因此，递归栈的空间复杂度为 $O(n)$。

综上，空间复杂度为：
$$空间复杂度=O(9\times n+n)=O(n)$$