No.3452 Divide Permutation
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2