No.1311 Reverse Permutation Index
レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限
: 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 :
ciel
/ テスター :
ngtkana
タグ : / 解いたユーザー数 98
作問者 :
ciel
/ テスター :
ngtkana
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。