結果
問題 | No.2513 Power Eraser |
ユーザー | 👑 amentorimaru |
提出日時 | 2023-06-16 12:21:26 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,827 ms / 6,000 ms |
コード長 | 2,089 bytes |
コンパイル時間 | 3,418 ms |
コンパイル使用メモリ | 135,160 KB |
実行使用メモリ | 54,396 KB |
最終ジャッジ日時 | 2023-10-20 21:03:58 |
合計ジャッジ時間 | 59,765 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 5 ms
4,348 KB |
testcase_04 | AC | 28 ms
4,632 KB |
testcase_05 | AC | 7 ms
4,348 KB |
testcase_06 | AC | 42 ms
5,688 KB |
testcase_07 | AC | 19 ms
4,508 KB |
testcase_08 | AC | 33 ms
4,676 KB |
testcase_09 | AC | 49 ms
5,724 KB |
testcase_10 | AC | 33 ms
4,664 KB |
testcase_11 | AC | 6 ms
4,348 KB |
testcase_12 | AC | 26 ms
4,556 KB |
testcase_13 | AC | 605 ms
25,844 KB |
testcase_14 | AC | 1,299 ms
48,660 KB |
testcase_15 | AC | 1,377 ms
49,784 KB |
testcase_16 | AC | 789 ms
28,016 KB |
testcase_17 | AC | 999 ms
30,544 KB |
testcase_18 | AC | 1,299 ms
48,612 KB |
testcase_19 | AC | 1,827 ms
54,364 KB |
testcase_20 | AC | 674 ms
26,756 KB |
testcase_21 | AC | 1,359 ms
49,668 KB |
testcase_22 | AC | 1,354 ms
49,648 KB |
testcase_23 | AC | 1,811 ms
54,396 KB |
testcase_24 | AC | 1,816 ms
54,396 KB |
testcase_25 | AC | 1,821 ms
54,396 KB |
testcase_26 | AC | 1,822 ms
54,396 KB |
testcase_27 | AC | 1,815 ms
54,396 KB |
testcase_28 | AC | 1,814 ms
54,396 KB |
testcase_29 | AC | 1,808 ms
54,396 KB |
testcase_30 | AC | 1,822 ms
54,396 KB |
testcase_31 | AC | 1,826 ms
54,396 KB |
testcase_32 | AC | 1,816 ms
54,396 KB |
testcase_33 | AC | 1 ms
4,348 KB |
testcase_34 | AC | 2 ms
4,348 KB |
testcase_35 | AC | 1,819 ms
54,396 KB |
testcase_36 | AC | 1,813 ms
54,396 KB |
7_evil_case_1.txt | AC | 4,171 ms
109,068 KB |
7_evil_case_2.txt | AC | 4,181 ms
109,068 KB |
7_evil_case_3.txt | AC | 4,174 ms
109,068 KB |
7_evil_case_4.txt | AC | 4,177 ms
109,068 KB |
7_evil_case_5.txt | AC | 4,176 ms
109,068 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include <atcoder/all> using namespace std; using ll = long long; using namespace atcoder; using mint2 = modint998244353; vector<mint2> rev(vector<mint2>& f, ll mod) { vector<mint2> res = { mint2(1) / f[0] }; ll t = 1; vector<mint2> ff; ff.reserve(f.size()); while (t < mod) { t *= 2; while (ff.size() < t && ff.size() < f.size()) { ff.push_back(f[ff.size()]); } auto m = convolution(convolution(res, res), f); vector<mint2> nres(t); for (ll i = 0; i < t; i++) { if (i < res.size()) nres[i] += 2 * res[i]; if (i < m.size()) nres[i] += -m[i]; } res = nres; } return res; } vector<mint2> div(vector<mint2>& f, vector<mint2>& g) { auto rf = f; auto rg = g; reverse(rf.begin(), rf.end()); reverse(rg.begin(), rg.end()); ll siz = f.size() - g.size() + 1; if (siz <= 0) return f; auto rv = rev(rg, siz); if (rf.size() > siz) rf.resize(siz); if (rv.size() > siz) rv.resize(siz); auto q = convolution(rf, rv); if (q.size() > siz) q.resize(siz); reverse(q.begin(), q.end()); auto gq = convolution(g, q); auto res = f; for (ll i = 0; i < res.size(); i++) { if (i < gq.size()) res[i] -= gq[i]; } while (res.back() == 0 && res.size() > 1) res.pop_back(); return res; } int main() { ll n; cin >> n; vector<ll> a(n); for (ll i = 0; i < n; i++) cin >> a[i]; ll m = 1; while (m < n) m *= 2; vector<mint2> def = { 1 }; vector<vector<mint2>> muls(m * 2, def); for (ll i = 0; i < n; i++) muls[i + m] = { a[i],-1 }; for (ll i = m - 1; i > 0; i--) muls[i] = convolution(muls[i * 2], muls[i * 2 + 1]); mint2 ans = 1; vector<vector<mint2>> divs(m * 2, def); for (ll i = 2; i < m + n; i++) { queue<ll> que; divs[i] = convolution(divs[i], divs[i / 2]); if (i % 2) divs[i] = convolution(muls[i - 1], divs[i]); divs[i] = div(divs[i], muls[i]); if (m <= i) ans *= divs[i][0]; } cout << ans.val() << endl; return 0; }