#P13689. [ARC121E] Directed Tree

    ID: 12891 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-容斥原理树形 DP树上背包倒序更新避免重复使用

[ARC121E] Directed Tree

题目描述

给定一棵有 NN 个顶点的有向树,顶点编号为 11 到 NN。

顶点 11 是这棵树的根。对于每个满足 2≤i≤N2 \leq i \leq N 的整数 ii,存在一条从顶点 pip_i 指向顶点 ii 的有向边。

设 aa 为 11 到 NN 的一个排列,aia_i 表示排列 aa 的第 ii 项。

所有可能的排列 aa 有 N!N! 种。请计算其中满足以下条件的排列数,并对 998244353998244353 取模:

  • 条件:对于任意 1≤i≤N1 \leq i \leq N,无法从顶点 aia_i 出发,经过至少一条边到达顶点 ii。

输入格式

输入通过标准输入给出,格式如下:

NN p2p_2 p3p_3 ⋯\cdots pNp_N

输出格式

输出满足题目条件的排列 aa 的个数,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

4
1 1 3

输出 #1

4

输入输出样例 #2

输入 #2

30
1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18

输出 #2

746746186

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤20001 \leq N \leq 2000
  • 1≤pi<i1 \leq p_i < i

样例说明 2

  • 别忘了对 998244353998244353 取模后输出答案。