No.2382 Amidakuji M
箱星
Kazun
問題文最終更新日: 2023-05-19 20:17:22
English (AI translation)
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 397 (群論コンテスト)
(順位表)
の他の問題:
Problem Statement
Initially, the sequence is $(1,2,\ldots,N)$.
Determine whether there exists a multiple $K$ of $M$ that satisfies the following condition, and if one exists, find the minimum value.
- The sequence can be made into $(P_1,P_2,\ldots,P_N)$ by performing the operation of swapping $2$ adjacent elements of the sequence exactly $K$ times.
Constraints
- $1\le N\le 2\times 10^5$
- $1\le M\le 10^{18}$
- $P$ is a permutation of $(1,2,\ldots,N)$
- All inputs are integers
Input
$N$ $M$ $P_1$ $P_2$ $\cdots$ $P_N$
Output
Output the minimum value of $K$. If no such value exists, output $-1$.
Sample
Sample 1
Input
4 3 4 1 3 2
Output
6
It can be done with $6$ operations, as in $(1,2,3,4)\to (2,1,3,4)\to (2,1,4,3)\to (2,4,1,3)\to (4,2,1,3)\to (4,1,2,3)\to (4,1,3,2)$. It cannot be done with $0,3$ operations.
Sample 2
Input
2 100 2 1
Output
-1
Sample 3
Input
3 987654321 1 2 3
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。