結果

問題 No.1311 Reverse Permutation Index
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:08:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 42 ms / 1,500 ms
コード長 1,985 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 54,392 KB
最終ジャッジ日時 2025-03-20 21:09:24
合計ジャッジ時間 989 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 1)  # 1-based indexing

    def update(self, idx, delta):
        # Convert to 1-based index
        idx += 1
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        # Sum from 0 to idx (0-based)
        idx += 1
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def query_range(self, a, b):
        if a > b:
            return 0
        return self.query(b) - (self.query(a - 1) if a > 0 else 0)

def main():
    import sys
    N, S = map(int, sys.stdin.readline().split())
    
    # Precompute factorials up to S-1!
    max_fact = S
    factorial = [1] * (max_fact)
    for i in range(1, max_fact):
        factorial[i] = factorial[i-1] * i
    
    # Step 1: Generate permutation from N
    def get_permutation(n, s):
        perm = []
        available = list(range(s))
        for i in range(s):
            remaining = s - i - 1
            fact = factorial[remaining] if remaining >=0 else 1
            k = n // fact
            selected = available[k]
            perm.append(selected)
            del available[k]
            n = n % fact
        return perm
    
    P = get_permutation(N, S)
    
    # Step 2: Compute inverse permutation
    inv_P = [0] * S
    for i in range(S):
        inv_P[P[i]] = i
    
    # Step 3: Compute the index of inv_P
    ft = FenwickTree(S)
    for i in range(S):
        ft.update(i, 1)
    
    m = 0
    for i in range(S):
        current = inv_P[i]
        remaining = S - i - 1
        fact = factorial[remaining] if remaining >= 0 else 1
        # Number of elements less than 'current' that are still available
        count = ft.query_range(0, current - 1)
        m += count * fact
        ft.update(current, -1)
    
    print(m)

if __name__ == '__main__':
    main()
0