P14928 [北大集训 2025] 深红

题目描述

给定正整数 $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

输入 #1

4 4 2
2 1

输出 #1

774
60

输入输出样例 #2

输入 #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$ 的一个排列。

【评分方式】

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