結果

問題 No.271 next_permutation (2)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:23:10
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,854 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 517,708 KB
最終ジャッジ日時 2025-06-12 13:27:03
合計ジャッジ時間 6,873 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    p = list(map(int, input[idx:idx+N]))
    idx += N

    if K == 0:
        print(0)
        return

    # Precompute factorial to check if K exceeds N!
    # For N >= 20, N! is way larger than 1e18
    if N > 20:
        # For N > 20, N! is larger than 1e18, so simulate K steps
        # But simulating K steps for N=1e5 is impossible, need another approach
        # However, this code cannot handle it, so we assume N is small
        pass

    # Function to compute next permutation and return delta inversion
    def next_permutation(arr):
        n = len(arr)
        inv = 0
        # Find the largest i such that arr[i] < arr[i+1]
        i = n - 2
        while i >= 0 and arr[i] >= arr[i+1]:
            i -= 1
        if i == -1:
            # Reverse the whole array
            return arr[::-1], (n*(n-1)//2) % MOD
        # Find the smallest j > i such that arr[j] > arr[i]
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        # Swap arr[i] and arr[j]
        arr[i], arr[j] = arr[j], arr[i]
        # Reverse arr[i+1:]
        arr[i+1:] = arr[i+1:][::-1]
        return arr, 0

    # Simulate steps until we find a cycle or reach K steps
    seen = {}
    current = p.copy()
    total = 0
    steps = 0
    cycle_invs = []
    inv_cache = []

    while steps < K:
        # Compute inversion number
        inv = 0
        fenwick = [0]*(N+2)
        for i in reversed(range(N)):
            x = current[i]
            tmp = 0
            while x > 0:
                tmp += fenwick[x]
                x -= x & -x
            inv += tmp
            x = current[i]
            while x <= N:
                fenwick[x] += 1
                x += x & -x
        inv %= MOD
        total = (total + inv) % MOD
        inv_cache.append(inv)
        steps += 1
        if steps == K:
            break
        # Compute next permutation
        current, delta = next_permutation(current)
        # Check if we have seen this permutation before
        t = tuple(current)
        if t in seen:
            # Found a cycle
            cycle_start = seen[t]
            cycle_length = steps - cycle_start
            cycle_sum = sum(inv_cache[cycle_start:steps]) % MOD
            remaining = K - cycle_start
            cycles = remaining // cycle_length
            total = (sum(inv_cache[:cycle_start]) + cycles * cycle_sum) % MOD
            remaining_steps = remaining % cycle_length
            for i in range(remaining_steps):
                total = (total + inv_cache[cycle_start + i]) % MOD
            print(total % MOD)
            return
        else:
            seen[t] = steps

    print(total % MOD)

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