Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1 から N までの番号がついた N 頂点からなる根付き木 T があります. 頂点 1 が根で,頂点 i (2 \leq i \leq N) の親は P_i (P_i < i) です.
(1,2,\cdots,N) の順列 x=(x_1,x_2,\cdots,x_N) が良い順列か否かは,以下の手順で判定されます.
- x に対する次の操作を考える.
- x の隣接する 2 要素 u,v であって,u,v が T 上で先祖子孫の関係にあるものを選ぶ.u,v のどちらが先祖でどちらが子孫でも構わない.そして,u,v を swap する.
- 上記の操作を 0 回以上行い,初期状態よりも辞書順で真に小さい順列を得ることが可能ならば,x は良い順列ではない.どう操作しても初期状態よりも辞書順で真に小さい順列が得られないなら,x は良い順列である.
正整数 B が与えられます. 順列 x に対し,\operatorname{hash}(x)=\sum_{1 \leq i \leq N} B^{i-1} \times x_i と定義します.
良い順列 x すべてに対する \operatorname{hash}(x) の総和を 998244353 で割ったあまりを求めてください.
数列の辞書順とは?
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは,下記の 1. と 2. のどちらかが成り立つことを言います. ここで,|S|, |T| はそれぞれ S, T の長さを表します.
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して,下記の 2 つがともに成り立つ.
- (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 を swap することで (1,3,2) というより小さい順列が得られるからです.
このサンプルでは,良い順列は x=(1,2,3),(1,3,2) の 2 つです. よって,\operatorname{hash}((1,2,3))+\operatorname{hash}((1,3,2))=30201+20301=50502 が答えになります.
入力例 2
5 100 1 2 3 4
出力例 2
504030201
このサンプルでは,どの 2 頂点をとってもそれらは先祖子孫の関係にあります. よって良い順列は 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
Score : 1200 points
Problem Statement
There is a rooted tree T with N vertices numbered from 1 to N. Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is P_i (P_i < i).
A permutation x = (x_1, x_2, \cdots, x_N) of (1, 2, \cdots, N) is judged to be a good permutation or not by the following criteria.
- Consider the following operation on x.
- Choose two adjacent elements u and v in x such that u and v are in an ancestor-descendant relationship in T. It does not matter which is the ancestor and which is the descendant. Then, swap u and v.
- If it is possible to obtain a permutation that is lexicographically strictly smaller than the initial state by performing the above operation zero or more times, x is not a good permutation. If it is impossible to obtain a permutation lexicographically smaller than the initial state by any such operations, x is a good permutation.
You are given a positive integer B. For a permutation x, define \operatorname{hash}(x) = \sum_{1 \leq i \leq N} B^{i-1} \times x_i.
Find the sum of \operatorname{hash}(x) over all good permutations x, modulo 998244353.
What is lexicographical order on sequences?
A sequence S = (S_1, S_2, \ldots, S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1, T_2, \ldots, T_{|T|}) if and only if 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
- There exists an integer 1 \leq i \leq \min\{ |S|, |T| \} such that the following two statements hold.
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- 2 \leq N \leq 100
- 1 \leq B < 998244353
- 1 \leq P_i < i (2 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N B P_2 P_3 \cdots P_N
Output
Print the answer.
Sample Input 1
3 100 1 1
Sample Output 1
50502
For example, x = (3, 1, 2) is not a good permutation, because by swapping 3 and 1, which are in an ancestor-descendant relationship, we can obtain (1, 3, 2), a lexicographically smaller permutation.
In this sample, the good permutations are x = (1, 2, 3) and x = (1, 3, 2). Thus, the answer is \operatorname{hash}((1,2,3)) + \operatorname{hash}((1,3,2)) = 30201 + 20301 = 50502.
Sample Input 2
5 100 1 2 3 4
Sample Output 2
504030201
In this sample, any two vertices are in an ancestor-descendant relationship. Therefore, the only good permutation is x = (1, 2, 3, 4, 5).
Sample Input 3
10 248730679 1 2 1 2 5 6 1 8 1
Sample Output 3
856673861
Sample Input 4
20 480124393 1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19
Sample Output 4
488941820