C - Tree Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 B=(B_1,\ldots,B_N) が良い数列であるとは，以下の条件を満たすことをいいます．

  • 任意の区間 [l,r]\ (1\leq l \leq r \leq N) に対して，以下の条件が成り立つような整数 x\ (l\leq x\leq r) が存在する：
    • 頂点に 1 から N の番号が付いた N 頂点 0 辺のグラフを用意する．全ての l \leq i \leq r について，i\neq x ならば頂点 i と頂点 B_i の間に辺を張る．このとき 頂点 l, l+1,\ldots,r が木をなしている．つまり，頂点 l, l+1,\ldots,r が連結になっている．

各要素が 1 以上 N 以下の整数，または -1 であるような数列 A=(A_1,\ldots,A_N) が与えられます．A のうち -1 であるような要素を 1 以上 N 以下の整数に置き換える方法であって，A が良い数列になるようなものの個数を 998244353 で割ったあまりを求めてください．

制約

  • 入力される数値は全て整数
  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq N または A_i=-1

入力

入力は以下の形式で標準入力から与えられる．

N 
A_1 \cdots A_N

出力

A のうち -1 であるような要素を 1 以上 N 以下の整数に置き換える方法であって，A が良い数列になるようなものの個数を 998244353 で割ったあまりを出力せよ．

入力例 1

3
-1 -1 -1

出力例 1

7

条件を満たす置き換え方は以下の 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

条件を満たす置き換え方は以下の 3 個です．

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

入力例 3

6
2 3 -1 -1 -1 -1

出力例 3

21

Score : 600 points

Problem Statement

A sequence B=(B_1,\ldots,B_N) of length N consisting of integers between 1 and N (inclusive) is called a good sequence if and only if it satisfies the following condition:

  • For every interval [l,r]\ (1\leq l \leq r \leq N), there exists an integer x\ (l\leq x\leq r) such that the following condition holds:
    • Prepare a graph with N vertices numbered from 1 to N and zero edges. For each l \leq i \leq r, if i\neq x, add an edge between vertices i and B_i. Then, vertices l, l+1,\ldots,r form a tree. That is, vertices l, l+1,\ldots,r are connected.

You are given a sequence A=(A_1,\ldots,A_N) where each element is either an integer between 1 and N, or -1. Find the number, modulo 998244353, of ways to replace the elements that are -1 in A with integers between 1 and N such that A becomes a good sequence.

Constraints

  • All input values are integers.
  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq N or A_i=-1

Input

The input is given from Standard Input in the following format:

N 
A_1 \cdots A_N

Output

Output the number, modulo 998244353, of ways to replace the elements that are -1 in A with integers between 1 and N (inclusive) such that A becomes a good sequence.

Sample Input 1

3
-1 -1 -1

Sample Output 1

7

The replacements that satisfy the condition are the following seven:

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

For example, in the case of A=(1,1,2), that the interval [1,2] satisfies the condition can be confirmed by setting x=1, where vertices 2 and A_2=1 are connected and vertices 1,2 form a tree.

Similarly, intervals [1,1],[2,2],[3,3],[2,3],[1,3] also satisfy the condition, so (1,1,2) is a good sequence.

Sample Input 2

3
-1 3 -1

Sample Output 2

3

The replacements that satisfy the condition are the following three:

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

Sample Input 3

6
2 3 -1 -1 -1 -1

Sample Output 3

21