F - Zonal Score Maximization 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

長さ 2 以上の正整数列のスコアをその数列の最大値と最小値の和で定義します。
長さ 2 以上の正整数列 A に対して、A を長さ 2 以上であるような 1 つ以上の連続部分列に分割したときに各連続部分列のスコアの総和としてあり得る値の最大値を f(A) とします。
より形式的には、ある正整数 K に対して長さが 2 以上であるような K 個の正整数列 B_1,B_2,\dots,B_K をこの順に連結させると A と同じ数列になるときに \sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right) としてあり得る値の最大値を f(A) とします。

各要素が 1 以上 N 以下の整数か -1 であるような長さ N の整数列 Q と、正整数 X が与えられます。
以下の条件をすべて満たすような (1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) の総数を 998244353 で割った余りを求めてください。

  • i=1,2,\dots,N について、Q_i \neq -1 ならば P_i=Q_i
  • f(P)=X

1 つの入力につき、T 個のテストケースを解いてください。

制約

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 10^5
  • 1 \leq X \leq 10^{18}
  • Q_i=-1 または 1 \leq Q_i \leq N
  • Q_i \neq -1 かつ Q_j \neq -1 ならば Q_i \neq Q_j\;(i \neq j)
  • すべてのテストケースにおける N の総和は 10^5 以下
  • 入力される値はすべて整数

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_t は以下の形式で与えられる。

N X  
Q_1 Q_2 \dots Q_N

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。

入力例 1

3
3 4
2 -1 -1
4 10
1 3 4 2
9 42
-1 -1 -1 -1 -1 -1 -1 -1 -1

出力例 1

2
1
155520

1 つ目のテストケースについて、1 つ目の条件を満たすような P は (2,1,3),(2,3,1) の 2 つです。
どちらの場合でも、P を長さ 2 以上であるような連続部分列に分割する方法は、P 自身のみからなる 1 つの連続部分列に分割するという方法しかありません。その場合のスコアの総和は 3+1=4 なので、f(P)=4 となります。
2 つ目のテストケースでは、P=(1,3,4,2) を (1,3) と (4,2) に分割するとスコアの総和は 10 となり、これ以上は大きくできないため、f(P)=10 となります。

Score : 800 points

Problem Statement

Define the score of a positive integer sequence with length 2 or more as the sum of its maximum and minimum values.
For a positive integer sequence A of length 2 or more, let f(A) be the maximum possible value of the total score of the contiguous subsequences when A is divided into one or more contiguous subsequences each of length 2 or more.
More formally, for a positive integer K, let f(A) be the maximum possible value of \sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right) when concatenating K positive integer sequences B_1, B_2, \dots, B_K, each of length 2 or more, in this order yields the same sequence as A.

You are given an integer sequence Q of length N where each element is either an integer between 1 and N inclusive or -1, and a positive integer X.
Find the total number, modulo 998244353, of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) satisfying all of the following conditions.

  • For i=1,2,\dots,N, if Q_i \neq -1 then P_i=Q_i.
  • f(P)=X

Solve T test cases per input.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 10^5
  • 1 \leq X \leq 10^{18}
  • Q_i=-1 or 1 \leq Q_i \leq N
  • If Q_i \neq -1 and Q_j \neq -1, then Q_i \neq Q_j\;(i \neq j).
  • The sum of N over all test cases is at most 10^5.
  • All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_t is given in the following format:

N X  
Q_1 Q_2 \dots Q_N

Output

Output the answers over a total of T lines. The t-th line should contain the answer for the t-th test case.

Sample Input 1

3
3 4
2 -1 -1
4 10
1 3 4 2
9 42
-1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 1

2
1
155520

For the first test case, the permutations P satisfying the first condition are these two: (2,1,3) and (2,3,1). In either case, the only way to divide P into contiguous subsequences each of length 2 or more is to take P itself as a single contiguous subsequence. The total score in that case is 3+1=4, so f(P)=4.
For the second test case, dividing P=(1,3,4,2) into (1,3) and (4,2) gives a total score of 10, which cannot be exceeded, so f(P)=10.