#P13671. [ARC140D] One to One

    ID: 12873 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-功能图普通并查集缩点贡献法计数 DP滚动数组倒序更新避免重复使用

[ARC140D] One to One

题目描述

对于所有元素都在 11 到 NN 之间的长度为 NN 的整数序列 X=(X1,X2,…,XN)X=(X_1,X_2,\dots,X_N),我们定义如下问题,并将其答案记为 f(X)f(X)。

有一个包含 NN 个顶点的无向图 GG。(GG 可能包含重边和自环。)GG 有 NN 条边,第 ii 条边连接顶点 ii 和顶点 XiX_i。请计算 GG 的连通分量个数。

给定一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N),其中每个 AiA_i 是 11 到 NN 之间的整数,或者是 −1-1。

请考虑所有满足 Ai≠−1⇒Ai=XiA_i\neq -1 \Rightarrow A_i = X_i 的、所有元素都在 11 到 NN 之间的长度为 NN 的整数序列 X=(X1,X2,…,XN)X=(X_1,X_2,\dots,X_N)。对于所有这样的 XX,计算 f(X)f(X) 的总和,并对 998244353998244353 取模后输出。

输入格式

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

NN A1A_1 A2A_2 …\dots ANA_N

输出格式

输出答案。

输入输出样例 #1

输入 #1

3
-1 1 3

输出 #1

5

输入输出样例 #2

输入 #2

1
1

输出 #2

1

输入输出样例 #3

输入 #3

8
-1 3 -1 -1 8 -1 -1 -1

输出 #3

433760

说明/提示

限制条件

  • 1≤N≤20001 \leq N \leq 2000
  • 每个 AiA_i 是 11 到 NN 之间的整数,或者是 −1-1。
  • 输入均为整数。

样例解释 1

满足条件的 XX 有以下 33 种情况。

  • 当 X=(1,1,3)X=(1,1,3) 时,答案为 22。
  • 当 X=(2,1,3)X=(2,1,3) 时,答案为 22。
  • 当 X=(3,1,3)X=(3,1,3) 时,答案为 11。

因此答案为 2+2+1=52+2+1=5。