問題一覧 > 通常問題

No.1311 Reverse Permutation Index

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 87
作問者 : cielciel / テスター : ngtkanangtkana
3 ProblemId : 887 / 出題時の順位表
問題文最終更新日: 2021-01-08 23:45:59

問題文

3 1 4 2 5
という順列は、
2 4 1 3 5
という置換を掛けることにより、
1 2 3 4 5
に戻すことができる。
この置換のことを逆置換と呼ぶことにしよう。

さて、3 1 4 2 5は、1 2 3 4 5を並び替えた順列中では辞書順で(00:55更新)50番目であり、2 4 1 3 5は36番目である(1 2 3 4 5は0番目とする)。このように、N 番目の順列の逆置換は何番目になるか、求めてほしい。

補足(必要ない限り読む必要はありません)

置換の定義は https://en.wikipedia.org/wiki/Permutation#One-line_notation です

入力

N S

N: 順列のインデックス
S: 順列の長さ

0 <= N < S! (< 264)
1 <= S <= 20

出力

逆置換の順列のインデックスを1行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
50 5
出力
36

サンプル2
入力
1234567890123456789 20
出力
2375759657264653994

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