結果

問題 No.616 へんなソート
ユーザー lam6er
提出日時 2025-03-20 21:11:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 421 ms / 2,000 ms
コード長 1,082 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 252,604 KB
最終ジャッジ日時 2025-03-20 21:11:35
合計ジャッジ時間 3,647 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, K = map(int, input().split())
a = list(map(int, input().split()))
a_sorted = sorted(a)
MOD = 10**9 + 7

# Initialize previous DP and prefix sum arrays
prev_dp = [0] * (K + 1)
prev_dp[0] = 1

prev_prefix_sum = [0] * (K + 2)
for k in range(K + 1):
    prev_prefix_sum[k + 1] = (prev_prefix_sum[k] + prev_dp[k]) % MOD

for i in range(1, n + 1):
    current_dp = [0] * (K + 1)
    max_d = i - 1  # Maximum possible increment in inversions for this step
    
    for k in range(K + 1):
        a_val = max(0, k - (i - 1))
        # Calculate the sum from a_val to k in previous step's dp
        sum_val = (prev_prefix_sum[min(k + 1, K + 1)] - prev_prefix_sum[a_val]) % MOD
        current_dp[k] = sum_val % MOD
    
    # Update the prefix sum for the current DP
    current_prefix_sum = [0] * (K + 2)
    for k in range(K + 1):
        current_prefix_sum[k + 1] = (current_prefix_sum[k] + current_dp[k]) % MOD
    
    prev_dp = current_dp
    prev_prefix_sum = current_prefix_sum

# The answer is the sum of all permutations with inversions <= K
print(prev_prefix_sum[K + 1] % MOD)
0