P8145 [JRKSJ R4] kth

> Always remember that you are a human, not an animal. Before eating corn-and-tomato stewed goat meat, you need to answer a question.

Given $n, m$, call an integer sequence “valid” (denote it by $s$) if: - The length of $s$ is $m$. - $\forall i\in[1,m], s_i\in[1,n]$. - $\forall i\in[2,m], |s_i-s_{i-1}|=1$. Given a permutation $p$ of $[1,n]$, define the “corresponding sequence” $s'$ of an integer sequence $s$ as follows: $s'$ has the same length as $s$. Let the length be $l$. Then $\forall i\in [1,l], s'_i=p_{s_i}$. Given $k$, among the corresponding sequences of all distinct valid integer sequences, find the sum of all elements of the $k$-th smallest corresponding sequence in lexicographical order, modulo $2^{32}$. If the $k$-th smallest corresponding sequence does not exist, output $-1$.

The first line contains three integers $n, m, k$.\ The second line contains $n$ integers representing $p$.

Output one integer, representing the answer.

**The input file of this problem is large, so please use an appropriate input method.** ### Sample Explanation For sample $1$, among the corresponding sequences of all distinct valid integer sequences, the three smallest in lexicographical order are: $$\{1,9,1,9,1,9\}$$ $$\{1,9,1,9,8,9\}$$ $$\{1,9,1,9,8,10\}$$ So the answer is $1+9+1+9+8+10=38$. For sample $2$, among the corresponding sequences of all distinct valid integer sequences, the two smallest in lexicographical order are: $$\{1,2,1,2,1\}$$ $$\{2,1,2,1,2\}$$ So the answer is $2+1+2+1+2=8$. ### Constraints | $\text{Subtask}$ | $n\le$ | $m\le$ | $k\le$ | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $10$ | $10^{18}$ | $5$ | | $2$ | $70$ | $70$ | $10^{18}$ | $15$ | | $3$ | $100$ | $300$ | $10^{18}$ | $20$ | | $4$ | $10^4$ | $10^4$ | $10^{18}$ | $15$ | | $5$ | $10^4$ | $10^{18}$ | $10^{18}$ | $10$ | | $6$ | $10^6$ | $10^{18}$ | $1$ | $5$ | | $7$ |$2\times10^7$| $10^{18}$ | $10^{18}$ | $30$ | For $100\%$ of the data, $1\le n\le 2\times10^7$, $2\le m\le 10^{18}$, $1\le k\le 10^{18}$. ### Special Scoring Method This problem uses subtask dependencies, as follows: - For subtasks $i\in\{1,6\}$, you only need to solve subtask $i$ correctly to get the score of subtask $i$. - For subtasks $i\in\{2,3,4,5,7\}$, you need to solve all subtasks $j\in[1,i]$ correctly to get the score of subtask $i$. Translated by ChatGPT 5