結果

問題 No.271 next_permutation (2)
ユーザー gew1fw
提出日時 2025-06-12 21:03:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,987 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 78,464 KB
最終ジャッジ日時 2025-06-12 21:05:14
合計ジャッジ時間 3,661 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 10**9 + 7

def compute_factorial(n):
    if n == 0:
        return 1
    res = 1
    for i in range(1, n+1):
        res = res * i
        if res > 1e18:
            return 0  # indicates overflow
    return res

def count_inversions(perm):
    n = len(perm)
    inv_count = 0
    for i in range(n):
        for j in range(i+1, n):
            if perm[i] > perm[j]:
                inv_count += 1
    return inv_count

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    p = list(map(int, sys.stdin.readline().split()))
    
    if K == 0:
        print(0)
        return
    
    M = compute_factorial(N)
    if M == 0:
        M = 0  # treat as very large
    
    if M == 0:
        # For large N, handle as per formula
        avg = (N * (N - 1) // 2) % MOD
        sum_total = (K * avg) % MOD
        print(sum_total)
        return
    
    S_total = (N * (N - 1) * M) // 4
    S_total %= MOD
    
    full_cycles = K // M
    remainder = K % M
    
    sum_full = (full_cycles * S_total) % MOD
    
    # Compute sum_remain
    sum_remain = 0
    current = p.copy()
    for _ in range(remainder):
        inv = count_inversions(current)
        sum_remain = (sum_remain + inv) % MOD
        # Compute next permutation
        # Find the largest index 'i' such that current[i] < current[i+1]
        i = N - 2
        while i >= 0 and current[i] >= current[i+1]:
            i -= 1
        if i == -1:
            # Reverse the entire array
            current = current[::-1]
        else:
            # Find largest j > i with current[j] > current[i]
            j = N - 1
            while current[j] <= current[i]:
                j -= 1
            # Swap
            current[i], current[j] = current[j], current[i]
            # Reverse suffix
            current[i+1:] = current[i+1:][::-1]
    
    total = (sum_full + sum_remain) % MOD
    print(total)

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