結果

問題 No.1311 Reverse Permutation Index
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-13 10:17:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 79 ms / 1,500 ms
コード長 1,760 bytes
コンパイル時間 1,502 ms
コンパイル使用メモリ 81,500 KB
実行使用メモリ 72,844 KB
最終ジャッジ日時 2023-10-18 10:55:25
合計ジャッジ時間 2,591 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
67,632 KB
testcase_01 AC 79 ms
72,836 KB
testcase_02 AC 74 ms
72,844 KB
testcase_03 AC 63 ms
67,696 KB
testcase_04 AC 61 ms
65,648 KB
testcase_05 AC 67 ms
70,632 KB
testcase_06 AC 75 ms
72,844 KB
testcase_07 AC 63 ms
67,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


from collections import Counter
from functools import lru_cache
from typing import List, Sequence, TypeVar


T = TypeVar("T", str, int)


@lru_cache(None)
def fac(n: int) -> int:
    if n <= 1:
        return 1
    return n * fac(n - 1)


def calRank(s: Sequence[T]) -> int:
    """求当前排列在所有排列中的字典序第几小(rank>=0)"""
    n = len(s)
    counter = Counter(s)
    keys = sorted(counter)
    res = 0
    for i, char in enumerate(s):
        suf = fac(n - i - 1)
        for count in counter.values():
            suf //= fac(count)  # !后面位置的组合数
        for smaller in keys:
            if smaller >= char:
                break
            res += counter[smaller] * suf
        counter[char] -= 1
    return res


def calPerm(s: Sequence[T], rank: int) -> List[T]:
    """求在所有排列中,字典序第几小(rank>=0)是谁"""
    n = len(s)
    counter = Counter(s)
    keys = sorted(counter)
    res = []
    for i in range(n):
        for char in keys:
            if counter[char] == 0:
                continue
            counter[char] -= 1
            suf = fac(n - i - 1)
            for count in counter.values():
                suf //= fac(count)  # !后面位置的组合数
            if suf > rank:
                res.append(char)
                break
            else:
                rank -= suf
                counter[char] += 1
    return res


# https://yukicoder.me/problems/no/1311
if __name__ == "__main__":

    # https://yukicoder.me/problems/no/1311
    # !求出1-n的排列中,字典序第k小的排列的`逆置换`的名次
    k, n = map(int, input().split())
    s = calPerm(list(range(1, n + 1)), k)
    rs = [s.index(i) + 1 for i in range(1, n + 1)]
    print(calRank(rs))
0