#P18894. [2026多校联测]排列
[2026多校联测]排列
题目描述
小 W 手上有两个长度为 的排列 , 。你需要求出有多少对 ,使得 且 ,称这样数对的数量为这两个排列的美丽度。
由于一些众所周知的原因,小 W 自闭了,忘记了 中的一些数字。你需要求出所有可能的 等概率出现时,美丽度的期望。由于小 W 还没学到实数,你只需要输出期望对 998244353 取模的结果即可。
输入格式
第一行一个正整数 ,表示排列的长度。
第二行 个正整数,表示 。
第三行 个正整数,表示 。如果 ,表示小 W 忘记了这个位置的数字。
输出格式
一行一个整数表示答案
样例 1 输入
4
1 3 2 4
-1 2 3 -1
样例 1 输出
499122179
样例 1 解释
有两种符合要求的 。若为 1, 2, 3, 4,那么美丽值为 5。若为 4, 2, 3, 1,那么美丽值为 0。
因此期望为
该组数据满足 。
数据范围
本题采用捆绑测试,只有通过一个 Subtask 内的所有数据才能获得这个 Subtask 的所有分数
对于所有数据,,保证 是个排列,且至少存在一个排列满足 的要求。
- Subtask1(10 points):
- Subtask2(10 points):
- Subtask3(20 points):,且 q 中没有−1。
- Subtask4(20 points):
- Subtask5(20 points):q 中没有−1。
- Subtask6(20 points):无特殊限制。