分数: 600 点
问题陈述
对于排列 P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N),我们定义 F(P) 通过以下程序:
-
有一个序列 B = (1, 2, \dots, N).
只要有一个整数 i 这样 B_i \lt P_{B_i},执行以下操作:- 让 j 是最小的整数 i 满足 B_i \lt P_{B_i}。然后,更换 B_j 与 P_{B_j}.
给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N。有多少种排列 P of (1,2,\dots,N) 满足 F(P) = A?求计数模数 998244353.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印数字,模数 998244353,排列 P 满足 F(P) = A.
示例输入 1
4 3 3 3 4
示例输出 1
1
例如,如果 P = (2, 3, 1, 4),那么 F(P) 确定为 (3, 3, 3, 4) 通过以下步骤:
- 最初, B = (1, 2, 3, 4).
- 最小整数 i 这样 B_i \lt P_{B_i} is 1。更换 B_1 与 P_{B_1} = 2, 制作 B = (2, 2, 3, 4).
- 最小整数 i 这样 B_i \lt P_{B_i} is 1。更换 B_1 与 P_{B_1} = 3, 制作 B = (3, 2, 3, 4).
- 最小整数 i 这样 B_i \lt P_{B_i} is 2。更换 B_2 与 P_{B_2} = 3, 制作 B = (3, 3, 3, 4).
- 没有更多了 i 满足 B_i \lt P_{B_i},因此该过程结束。目前的 B = (3, 3, 3, 4) 定义为 F(P).
只有一种排列 P 这样 F(P) = A,即 (2, 3, 1, 4).
示例输入 2
4 2 2 4 3
示例输出 2
0
示例输入 3
8 6 6 8 4 5 6 8 8
示例输出 3
18