← 返回题目列表

AtCoder · arc223_f

F. 区域分数最大化

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

分数: 800 点

问题陈述

定义有长度的正整数序列的分数 2 或更多作为其最大值和最小值的总和。
对于正整数序列 A 长度 2 或更多,让 f(A) 为连续子序列总分的最大可能值 A 被分为一个或多个连续的子序列,每个子序列的长度 2 或更多。
更正式地说,对于正整数 K,让 f(A) 是最大可能值 \sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right) 连接时 K 正整数序列 B_1, B_2, \dots, B_K,每个长度 2 或更多,按此顺序产生与 A.

给你一个整数序列 Q 长度 N 其中每个元素是介于 1 和 N (含)或 -1,和一个正整数 X.
求总数,取模 998244353,排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) 满足以下所有条件。

  • 对于 i=1,2,\dots,N,如果 Q_i \neq -1 然后 P_i=Q_i.
  • f(P)=X

解决 T 每个输入的测试用例。

约束

  • 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 和 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

对于第一个测试用例,排列 P 满足第一个条件的是这两个: (2,1,3) 和 (2,3,1)。 无论哪种情况,唯一的划分方法 P 成每个长度的连续子序列 2 以上是采取 P 本身作为单个连续子序列。这种情况下的总分是 3+1=4,所以 f(P)=4.
对于第二个测试用例,除 P=(1,3,4,2) 进入 (1,3) 和 (4,2) 给出的总分是 10,不能超过,所以 f(P)=10.