分数: 575 点
问题陈述
有一个盒子,里面装有 N 球编号 1 通过 N。每个球都涂有一种以整数表示的颜色,并且球 i 涂有颜色 C_i.
高桥表演 N 操作。的 k第次操作 (1\le k\le N) 如下:
- 从盒子里均匀随机抽取一个球并将其丢弃。如果抽出的球有颜色 G_k,增益 1 点。
求概率,模 998244353,表示总分超过 N 操作是 0 点。
概率模的定义 998244353
可以证明,求的概率总是有理数。此外,在该问题的约束下,当有理数表示为不可约分数时 \frac{P}{Q},可以证明 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,存在一个唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.
约束
- 1\le N\le 2\times 10^5
- 1\le C_i,G_k\le N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C_1 C_2 \ldots C_N G_1 G_2 \ldots G_N
输出
输出求模概率 998244353.
示例输入 1
3 1 2 3 1 1 2
示例输出 1
332748118
例如,操作可以进行如下:
- 第一次操作:有颜色的球 2 是从盒子里抽出来的。
- 第二次操作:有颜色的球 1 是从盒子里取出的。增益 1 点。
- 第三次操作:有颜色的球 3 是从盒子里抽出来的。
在这种情况下,总分是 1 点。
高桥总得分为的概率 0 is \displaystyle \frac13.
示例输入 2
3 1 1 3 3 3 3
示例输出 2
0
高桥的总分始终是 1 点。
示例输入 3
6 1 2 3 3 4 5 3 5 3 5 5 4
示例输出 3
316110712