#P18894. [2026多校联测]排列

[2026多校联测]排列

题目描述

小 W 手上有两个长度为 nn 的排列 {pi}\{p_i\}, {qi}\{q_i\}。你需要求出有多少对 i<ji < j,使得 pi<pjp_i < p_j 且 qi<qjq_i < q_j ,称这样数对的数量为这两个排列的美丽度。

由于一些众所周知的原因,小 W 自闭了,忘记了 {qi}\{q_i\} 中的一些数字。你需要求出所有可能的 {qi}\{q_i\} 等概率出现时,美丽度的期望。由于小 W 还没学到实数,你只需要输出期望对 998244353 取模的结果即可。

输入格式

第一行一个正整数 nn,表示排列的长度。

第二行 nn 个正整数,表示 pip_i。

第三行 nn 个正整数,表示 qiq_i。如果 qi=−1q_i =−1,表示小 W 忘记了这个位置的数字。

输出格式

一行一个整数表示答案

样例 1 输入

4
1 3 2 4
-1 2 3 -1

样例 1 输出

499122179

样例 1 解释

有两种符合要求的 qq。若为 1, 2, 3, 4,那么美丽值为 5。若为 4, 2, 3, 1,那么美丽值为 0。

因此期望为 5+02≡499122179(mod998244353)\frac{5+0}{2} ≡ 499122179 \pmod{998244353}

该组数据满足 n=5000n = 5000。

数据范围

本题采用捆绑测试,只有通过一个 Subtask 内的所有数据才能获得这个 Subtask 的所有分数

对于所有数据,1≤n≤1061 \leq n \leq 10^6,保证 pp 是个排列,且至少存在一个排列满足 qq 的要求。

  • Subtask1(10 points):n≤10n \leq 10
  • Subtask2(10 points):n≤5000n \leq 5000
  • Subtask3(20 points):n≤105n \leq 10^5,且 q 中没有−1。
  • Subtask4(20 points):n≤105n \leq 10^5
  • Subtask5(20 points):q 中没有−1。
  • Subtask6(20 points):无特殊限制。