結果
問題 | No.1621 Sequence Inversions |
ユーザー |
![]() |
提出日時 | 2021-07-22 23:13:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,977 ms / 3,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 134 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 129,660 KB |
最終ジャッジ日時 | 2024-07-17 19:58:37 |
合計ジャッジ時間 | 22,494 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
mod = 998244353 eps = 10**-9 def main(): import sys from collections import Counter input = sys.stdin.readline def calc_k(x, y): res = [0] * (x * y + 1) dp = [[[0] * (x * y + 1) for _ in range(x+1)] for _ in range(y + 1)] dp[0][0][0] = 1 for i in range(y): for j in range(x+1): for k in range(j, x+1): for lv in range(x*y+1): lv_new = lv + k if lv_new <= x*y: dp[i+1][k][lv_new] = (dp[i+1][k][lv_new] + dp[i][j][lv])%mod for j in range(x+1): for lv in range(x*y+1): res[lv] = (res[lv] + dp[-1][j][lv]) % mod return res N, K = map(int, input().split()) A = list(map(int, input().split())) A.sort(reverse=True) C = Counter(A) D = {} for a in C: D[a] = 0 inv_max = N * (N - 1) // 2 dp = [[0] * (inv_max+1) for _ in range(N+1)] dp[0][0] = 1 for i in range(N): a = A[i] if D[a]: dp[i+1] = dp[i] continue R = calc_k(i, C[a]) for inv in range(inv_max + 1): for j, r in enumerate(R): inv_new = inv + j if inv_new <= inv_max: dp[i+1][inv_new] = (dp[i+1][inv_new] + dp[i][inv] * r)%mod D[a] += 1 print(dp[-1][K]) if __name__ == '__main__': main()