← 返回题目列表

AtCoder · arc140_d

D. 一对一

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

对于整数序列 X=(X_1,X_2,\dots,X_N) 长度 N 其元素都在 1 和 N (含),考虑下面的问题,并让 f(X) 就是答案。

有一个无向图 G 与 N 顶点(可能还有多边和自循环)。 G 有 N 边缘, i- 第一个连接顶点 i 和顶点 X_i。找出连通分量的数量 G.

给你一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N,其中每个 A_i 是介于 1 和 N (含)或 -1.

考虑一个整数序列 X=(X_1,X_2,\dots,X_N) 长度 N 其元素都在 1 和 N 这样 A_i \neq -1 \Rightarrow A_i = X_i。求总和 f(X) 综上所述 X,模数 998244353.

约束

  • 1 \le N \le 2000
  • A_i 介于 1 和 N (含)或 -1.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3
-1 1 3

示例输出 1

5

共有三个序列 X 满足要求,如下。

  • X=(1,1,3),问题的答案是 黑板上写着 2.
  • X=(2,1,3),问题的答案是 黑板上写着 2.
  • X=(3,1,3),问题的答案是 黑板上写着 1.

因此,答案是 2+2+1=5.


示例输入 2

1
1

示例输出 2

1

示例输入 3

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

示例输出 3

433760