問題一覧 > 通常問題

No.3452 Divide Permutation

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 12974 / 自分の提出
問題文最終更新日: 2026-02-20 19:14:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 493 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a permutation $P = (P_{1}, P_{2}, \dots, P_{N})$ of $(1, 2, \dots , N)$.

For each $k = 1, 2, \dots, N$, answer the following question.

  • Among the permutations of $(1, 2, \dots, N)$ that can be obtained by splitting $P$ into exactly $k$ non-empty contiguous subarrays, rearranging them, and then concatenating them, find the rolling hash of the lexicographically smallest one.

Here, the rolling hash of a sequence of positive integers $a = (a_{1}, a_{2}, \dots, a_{n})$ is defined as $\displaystyle\sum_{i = 1}^{n}a_{i}\cdot 10^{n - i}\pmod{998244353}$.

You are given $T$ test cases; solve each of them.

Constraints

  • $1\leq T\leq 2\times 10^{5}$
  • $1\leq N\leq 2\times 10^{5}$
  • $P$ is a permutation of $(1, 2, \dots, N)$
  • The sum of $N$ over the $T$ test cases is at most $2\times 10^{5}$
  • All input values are integers

Input

$T$
$case_{1}$
$case_{2}$
$\vdots$
$case_{T}$

Here, $case_{i}$ represents the $i$-th test case, given in the following format.

$N$
$P_{1}$ $P_{2}$ $\dots$ $P_{N}$

Output

Print $T$ lines.

On the $i$-th line, print the answers for $k = 1, 2, \dots, N$ of the $i$-th test case, in this order, separated by spaces.

Sample

Sample 1
Input
4
3
3 1 2
4
4 2 1 3
5
2 5 1 4 3
8
5 8 1 7 6 2 4 3
Output
312 123 123
4213 1342 1324 1234
25143 14325 12543 12435 12345
58176243 17624358 15876243 12435876 12435768 12345876 12345768 12345678

Consider $k = 2$ in the $2$-nd test case. Splitting $P = (4, 2, 1, 3)$ into $(4, 2), (1, 3)$, rearranging them as $(1, 3), (4, 2)$, and concatenating them gives $(1, 3, 4, 2)$. The lexicographically smallest permutation obtainable is $(1, 3, 4, 2)$, so print $1342$, the rolling hash of $(1, 3, 4, 2)$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。