← 返回题目列表

AtCoder · agc068_d

D. Lexmin 的哈希值总和

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

有一棵有根的树 T 与 N 顶点编号自 1 to N。 顶点 1 是根,也是顶点的父级 i (2 \leq i \leq N) 是 P_i (P_i < i).

排列 x = (x_1, x_2, \cdots, x_N) of (1, 2, \cdots, N) 被判断为 好 排列与否按以下标准。

  • 考虑以下操作 x.
    • 选择两个相邻元素 u 和 v in x 这样 u 和 v 处于祖先-后代关系 T。谁是祖先、谁是后代并不重要。然后,交换 u 和 v.
  • 如果可以通过执行上述操作零次或多次来获得按字典顺序严格小于初始状态的排列, x is 不 一个很好的排列。如果不可能通过任何此类操作获得按字典顺序小于初始状态的排列, x 是一个很好的排列。

给你一个正整数 B。 对于排列 x,定义 \operatorname{hash}(x) = \sum_{1 \leq i \leq N} B^{i-1} \times x_i.

求总和 \operatorname{hash}(x) 总体上良好的排列 x,模数 998244353.

序列的字典顺序是什么?

一个序列 S = (S_1, S_2, \ldots, S_{|S|}) 据说是 按字典顺序较小 比序列 T = (T_1, T_2, \ldots, T_{|T|}) 当且仅当下面的 1. 或 2. 成立。 在这里, |S| 和 |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\{ |S|, |T| \} 使得以下两个陈述成立。
    • (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1}).
    • S_i 小于 T_i (作为数字)。

约束

  • 2 \leq N \leq 100
  • 1 \leq B < 998244353
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N B
P_2 P_3 \cdots P_N

输出

打印答案。


示例输入 1

3 100
1 1

示例输出 1

50502

例如, x = (3, 1, 2) 不是一个好的排列,因为通过交换 3 和 1,处于祖先-后代关系,我们可以得到 (1, 3, 2),字典顺序较小的排列。

在此示例中,好的排列是 x = (1, 2, 3) 和 x = (1, 3, 2)。 因此,答案是 \operatorname{hash}((1,2,3)) + \operatorname{hash}((1,3,2)) = 30201 + 20301 = 50502.


示例输入 2

5 100
1 2 3 4

示例输出 2

504030201

在此示例中,任何两个顶点都存在祖先-后代关系。 因此,唯一好的排列是 x = (1, 2, 3, 4, 5).


示例输入 3

10 248730679
1 2 1 2 5 6 1 8 1

示例输出 3

856673861

示例输入 4

20 480124393
1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19

示例输出 4

488941820