[R16F]知识点学习3 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个知识点，想学习第 $i$ 个知识点，必须先学习第 $p_i$ 个知识点，我们称 $p_i$ 是 $i$ 的前置知识点。保证 $p_i< i$，如果 $p_i=0$ 说明第 $i$ 个知识点可以直接学习。

定义合法的学习方案为学习完这 $n$ 个知识点的顺序，满足知识点 $p_i$ 在知识点 $i$ 前学习。

给定一个合法的学习方案 $A$，求有多少种字典序小于 $A$ 的合法的学习方案，对 $998244353$ 取模。

对于两个合法的学习方案 $X$ 和 $Y$，如果 $X_i<Y_i$ 且对于 $j<i$ 均有 $X_j=Y_j$，那么我们称 $X$ 的字典序小于 $Y$。

格式

输入格式

第一行包含一个整数 $n$，表示知识点的数量。

第二行包含 $n$ 个整数 $p_i$，分别表示每个知识点的前置知识点。

第三行包含 $n$ 个整数 $A_i$，表示给定的学习方案。数据保证 $A$ 是一个合法的学习方案。

输出格式

输出一个整数表示字典序小于 $A$ 的合法的学习方案的数量，对 $998244353$ 取模。

样例

样例输入 #1

6
0 1 0 3 1 5
3 1 5 2 4 6

样例输出 #1

36

样例输入 #2

6
0 1 0 3 1 5
1 2 3 4 5 6

样例输出 #2

0

数据规模

对于 $10\%$ 的数据， $n\leq 10$。

对于 $30\%$ 的数据， $n\leq 200$。

对于 $60\%$ 的数据， $n\leq 3000$。

对于 $100\%$ 的数据， $1\leq n\leq 4\times 10^5$，$0\leq p_i< i$，$1\leq A_i\leq n$。数据保证 $A$ 是一个合法的学习方案。