問題一覧 > 通常問題

No.271 next_permutation (2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : antaanta
3 ProblemId : 336 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:04

問題文

ある$n$に対する$[1,2,\ldots,n]$の置換(permutation) $x$に対し、$f(x)$を辞書順で$x$の次の置換とする。 ただし、$x$が辞書順で最後のもの$[n,n-1, \ldots, 1]$である場合は、$f(x)$を辞書順で最初のもの$[1,2,\ldots,n]$として定義する。 たとえば、$f([1, 2, 3]) = [1, 3, 2]$, $f(f([3,1,2])) = f([3,2,1]) = [1,2,3]$ となる。

置換$x$の転倒数(inversion number)を${\rm inv}(x)$と表す。 たとえば、${\rm inv}([2,1,3]) = 1, {\rm inv}([3,2,1]) = 3$である。

置換$p$が与えられたとき、置換の列$A$を、$A_0 = p$, $A_i = f(A_{i-1})$ ($i \in [1,2,\ldots]$) として定義する。 つまり、$A_i$は$p$に$f$を$i$回適用したものである。 たとえば、$p = [2,1,3]$ なら $A = [[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$ となる。 $A$の添字は0から始まることに注意せよ。

整数$N$, 整数$K$, 長さ$N$の置換$p$が入力として与えられる。$\displaystyle \sum_{i=0}^{K-1} {\rm inv}(A_i)$を$1000000007$で割った余りを求めよ。

入力

$N$ $K$
$p_1$ $p_2$ $\ldots$ $p_N$

1行目に、整数$N (1 \le N \le 10^5)$, 整数$K (0 \le K \le 10^{18})$が空白区切りで与えられる。 2行目に、長さ$N$の$[1,2,\ldots,N]$の置換$p (1 \le p_i \le N)$が空白区切りで与えられる。

出力

$\displaystyle \sum_{i=0}^{K-1} {\rm inv}(A_i)$を$1000000007$で割った余りを1行に出力せよ。

サンプル

サンプル1
入力
3 5
2 1 3
出力
8

問題文にある$A$の例である。それぞれの${\rm inv}$は$[1, 2, 2, 3, 0]$となるので、その総和の$8$が答えとなる。

サンプル2
入力
3 36
1 2 3
出力
54

この場合、$A$は長さ$3! = 6$の周期で巡回する。1周期の${\rm inv}$和が$9$であるので、$9 \times \frac{36}{6} = 54$が答えとなる。

サンプル3
入力
1 1000000000000000000
1
出力
0

サンプル4
入力
2 1000000000000000000
1 2
出力
500000028

$1000000007$で割った余りを出力することに注意せよ。

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