4339. [国家集训队 2026]深红

【题目描述】

给定正整数 $n, m, k$ 以及 $1 \sim k$ 的排列 $p$。

称一个大小为 $n \times m$，元素均为 $[1, k]$ 中的正整数的矩阵为一幅画。对于一幅画 $A$，定义 $A_{i,j}$ 为这个矩阵从上到下第 $i$ 行，从左到右第 $j$ 列的位置的值。

定义两幅画 $A, B$ **相同**，当且仅当对于所有 $1 \le i \le n$，$1 \le j \le m$，均有 $A_{i,j} = B_{i,j}$。以下将两幅画 $A, B$ 相同记作 $A = B$。

定义两幅画 $A, B$ **相似**，当且仅当 $A$ 进行若干次如下两种变换之一可以得到 $B$：

1. 将 $A$ 的第一行移动至最后一行；

2. 将 $A$ 的第一列移动至最后一列。

以下将两幅画 $A, B$ 相似记作 $A \sim B$。

可以证明，二元关系相同和相似均构成等价关系。

对于一幅画 $A$，定义 $f(A)$ 也是一幅画，其中 $f(A)_{i,j} = p_{A_{i,j}}$ ($1 \le i \le n$, $1 \le j \le m$)。

定义一幅画 $A$ 是**优美的**，当且仅当 $f(A) \sim A$。

你需要回答以下两个问题：

1. 最多能选出多少幅优美的画，使得它们**互不相同**？

2. 最多能选出多少幅优美的画，使得它们**互不相似**？

由于答案可能较大，你只要求求出答案对 $998,244,353$ 取模后的结果。

【输入格式】

输入的第一行包含三个正整数 $n, m, k$，表示画的大小与值域。  

输入的第二行包含 $k$ 个正整数 $p_1, p_2, \dots, p_k$，表示给定的排列。

【输出格式】

输出两行两个非负整数，分别表示最多能选出的**互不相同**与**互不相似**的优美的画的数量对 $998,244,353$ 取模后的结果。  

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

【样例 1 输入】

4 4 2
2 1

【样例 1 输出】

774
60

【样例 2 输入】

8 10 3
1 2 3

【样例 2 输出】

412733925
108590870

【数据规模与约定】

对于所有测试数据，均有：  

- $1 \le n, m \le 10^3$，$1 \le k \le 10^6$；  

- 对于所有 $1 \le i \le k$，$1 \le p_i \le k$，且 $p_1, p_2, \dots, p_k$ 是 $1 \sim k$ 的一个排列。

【评分方式】

对于每个子任务：  

- 正确回答所有测试数据的最多能选出的**互不相同**的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $70\%$ 的分数；  

- 正确回答所有测试数据的最多能选出的**互不相似**的优美的画的数量对 $998,244,353$ 取模后的结果，可获得该子任务 $30\%$ 的分数。  

注意：即使选手仅回答了其中一个问题，也需要按照输出格式输出两个整数，分别对应两个问题的答案。

为了方便COGS评分，正确回答测试点的一个答案给$50\%$的分数。

【来源】

IOI2026中国国家集训队集中培训 Day2 Task1