結果
問題 | No.1621 Sequence Inversions |
ユーザー |
![]() |
提出日時 | 2021-07-22 22:38:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 3,000 ms |
コード長 | 1,358 bytes |
コンパイル時間 | 2,170 ms |
コンパイル使用メモリ | 207,804 KB |
最終ジャッジ日時 | 2025-01-23 07:06:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (auto &&x : a) { cin >> x; } sort(a.begin(), a.end()); auto acopy = a; acopy.erase(unique(acopy.begin(), acopy.end()), acopy.end()); for (auto &&x : a) { x = lower_bound(acopy.begin(), acopy.end(), x) - acopy.begin(); } vector<int> acount(n); for (auto &&x : a) { acount.at(x)++; } vector dp(n + 1, vector<mint>(k + 1)); dp.at(0).at(0) = 1; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { for (int jnew = j; jnew <= min(k, j + i); jnew++) { dp.at(i + 1).at(jnew) += dp.at(i).at(j); } } } auto ans = dp.at(n); for (int i = 0; i < n; i++) { int64_t d = acount.at(i); if (d <= 1) { continue; } for (int j = 0; j <= k; j++) { mint x = ans.at(j); for (int jnew = j + 1; jnew <= min(int64_t(k), j + d * (d - 1) / 2); jnew++) { ans.at(jnew) -= x * dp.at(d).at(jnew - j); } } } cout << ans.at(k).val() << endl; return 0; }