結果
問題 |
No.616 へんなソート
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)