結果

問題 No.271 next_permutation (2)
ユーザー lam6er
提出日時 2025-03-20 20:17:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,866 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 92,580 KB
最終ジャッジ日時 2025-03-20 20:18:36
合計ジャッジ時間 6,511 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def next_permutation(seq):
    seq = list(seq)
    k = len(seq) - 2
    while k >= 0 and seq[k] >= seq[k + 1]:
        k -= 1
    if k < 0:
        return None  # current is the last permutation
    l = len(seq) - 1
    while seq[l] <= seq[k]:
        l -= 1
    seq[k], seq[l] = seq[l], seq[k]
    seq[k + 1:] = reversed(seq[k + 1:])
    return tuple(seq)

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

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    K = int(data[1])
    if K == 0:
        print(0)
        return
    p = tuple(map(int, data[2:2 + n]))
    
    cycle = []
    seen = {}
    current = p
    sum_total = 0
    cycle_found = False
    steps = 0
    
    while steps < K:
        if current in seen:
            start_idx = seen[current]
            cycle_length = steps - start_idx
            remaining = K - start_idx
            full_cycles = remaining // cycle_length
            remainder = remaining % cycle_length
            sum_pre = sum(cycle[:start_idx])
            sum_cycle = sum(cycle[start_idx:steps])
            sum_total = sum_pre + full_cycles * sum_cycle
            sum_total += sum(cycle[start_idx:start_idx + remainder])
            cycle_found = True
            break
        seen[current] = steps
        inv = compute_inversion_count(current)
        cycle.append(inv)
        steps += 1
        # Compute next permutation
        next_p = next_permutation(current)
        if next_p is None:
            next_p = tuple(sorted(current))
        current = next_p
    
    if not cycle_found:
        sum_total = sum(cycle[:K])
    
    print(sum_total % MOD)

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