← 返回题目列表

AtCoder · arc206_c

C. 树序列

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

分数: 600 点

问题陈述

一个序列 B=(B_1,\ldots,B_N) 长度 N 由之间的整数组成 1 和 N (含)当且仅当满足以下条件时才称为好序列:

  • 对于每个间隔 [l,r]\ (1\leq l \leq r \leq N),存在一个整数 x\ (l\leq x\leq r) 使得以下条件成立:
    • 准备一个图表 N 顶点编号自 1 to N 和零边缘。对于每个 l \leq i \leq r,如果 i\neq x,在顶点之间添加一条边 i 和 B_i。然后,顶点 l, l+1,\ldots,r 形成一棵树。也就是说,顶点 l, l+1,\ldots,r 已连接。

给你一个序列 A=(A_1,\ldots,A_N) 其中每个元素是介于 1 和 N,或 -1。求模数 998244353,替换元素的方法 -1 in A 之间的整数 1 和 N 这样 A 成为一个好的序列。

约束

  • 所有输入值均为整数。
  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq N or A_i=-1

输入

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

N 
A_1 \cdots A_N

输出

输出数字,模数 998244353,替换元素的方法 -1 in A 之间的整数 1 和 N (含)使得 A 成为一个好的序列。


示例输入 1

3
-1 -1 -1

示例输出 1

7

满足条件的替换有以下七种:

  • (1,1,2)
  • (2,1,2)
  • (2,2,2)
  • (2,3,1)
  • (2,3,2)
  • (2,3,3)
  • (3,1,2)

例如,在以下情况 A=(1,1,2),即间隔 [1,2] 满足条件可以通过设置来确认 x=1,其中顶点 2 和 A_2=1 已连接且顶点 1,2 形成一棵树。

同样,间隔 [1,1],[2,2],[3,3],[2,3],[1,3] 也满足条件,所以 (1,1,2) 是一个很好的序列。


示例输入 2

3
-1 3 -1

示例输出 2

3

满足条件的替换有以下三个:

  • (2,3,1)
  • (2,3,2)
  • (2,3,3)

示例输入 3

6
2 3 -1 -1 -1 -1

示例输出 3

21