F. Zonal Score Maximization

Zonal Score Maximization

AtCoder

⌀ 3156

Zonal Score MaximizationAI (CI翻译)

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.

{"titleZh":"区域得分最大化","bodyZh":"## 题目描述\n\n定义一个长度为 $2$ 或更长的正整数序列的得分为其最大值与最小值之和。\n对于一个长度为 $2$ 或更长的正整数序列 $A$ ，令 $f(A)$ 表示将 $A$ 划分为一个或多个长度均为 $2$ 或更长的连续子序列后，这些连续子序列的得分总和可能达到的最大值。\n更形式化地说，对于正整数 $K$ ，令 $f(A)$ 表示满足以下条件的 $\sum_{k=1}^{K}\\left(\\max(B_k)+\\min(B_k)\\right)$ 的最大值：按顺序连接 $K$ 个正整数序列 $B_1, B_2, \\dots, B_K$ 后得到的序列与 $A$ 相同，且每个序列的长度都为 $2$ 或更长。\n\n给定一个长度为 $N$ 的整数序列 $Q$ ，其中每个元素要么是 $1$ 到 $N$ 之间的整数，要么是 $-1$ ，以及一个正整数 $X$ 。\n求满足以下所有条件的 $(1,2,\\dots,N)$ 的排列 $P=(P_1,P_2,\\dots,P_N)$ 的总数，并将答案对 $998244353$ 取模。\n\n- 对于 $i=1,2,\\dots,N$ ，如果 $Q_i \\neq -1$ ，则 $P_i=Q_i$ 。\n- $f(P)=X$ 。\n\n请解决 $T$ 组测试数据。\n\n## 约束条件\n\n- $1 \\leq T \\leq 10^5$ \n- $2 \\leq N \\leq 10^5$ \n- $1 \\leq X \\leq 10^{18}$ \n- $Q_i=-1$ 或 $1 \\leq Q_i \\leq N$ \n- 如果 $Q_i \\neq -1$ 且 $Q_j \\neq -1$ ，则 $Q_i \\neq Q_j\\;(i \\neq j)$ 。\n- 所有测试数据中的 $N$ 之和不超过 $10^5$ 。\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入读入，格式如下：\n\n\nT\n\\mathrm{case}_1\n\\mathrm{case}_2\n\\vdots\n\\mathrm{case}_T\n`\n\n每组测试数据 $\\mathrm{case}_t$ 的格式如下：\n\n`\nN X\nQ_1 Q_2 \\dots Q_N\n\n\n## 输出格式\n\n输出共 $T$ 行答案。第 $t$ 行应包含第 $t$ 组测试数据的答案。"}AI (CI翻译)

样例

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

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$.

题目信息

题号

arc223_f

所属比赛

AtCoder Regular Contest 223

时间限制

4 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。