結果
問題 | No.2513 Power Eraser |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-16 13:32:43 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,109 ms / 6,000 ms |
コード長 | 2,211 bytes |
コンパイル時間 | 3,706 ms |
コンパイル使用メモリ | 144,000 KB |
実行使用メモリ | 64,420 KB |
最終ジャッジ日時 | 2024-09-20 17:06:02 |
合計ジャッジ時間 | 114,653 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 TLE * 5 |
ソースコード
#include<iostream> #include<algorithm> #include <atcoder/all> using namespace std; using namespace atcoder; using mint2 = modint998244353; using ll = long long; vector<mint2> rev(vector<mint2>& f, ll mod) { vector<mint2> res = { mint2(1) / f[0] }; ll t = 1; while (t < mod) { t *= 2; auto m = convolution(res, res); m = convolution(m, 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; auto q = convolution(rf, rev(rg, 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; } ll n; vector<ll> a; mint2 solve2(ll l1, ll l2, ll d) { ll m = 1; while (m < d) { m *= 2; } vector<ll> a1(d), a2(d); for (ll i = 0; i < d; i++) { a1[i] = a[l1 + i]; a2[i] = a[l2 + i]; } vector<mint2> def = { 1 }; vector<vector<mint2>> f1(m * 2, def), f2(m * 2, def); for (ll i = 0; i < d; i++) { f1[i + m] = { a1[i],-1 }; f2[i + m] = { a2[i],-1 }; } for (ll i = m - 1; i >= 1; i--) { f1[i] = convolution(f1[i * 2], f1[i * 2 + 1]); f2[i] = convolution(f2[i * 2], f2[i * 2 + 1]); } f1[1] = div(f1[1], f2[1]); for (ll i = 2; i < 2 * m; i++) { auto& p = f1[i / 2]; if (f2[i].size() != 1) f1[i] = div(p, f2[i]); } mint2 res = 1; for (ll i = 0; i < d; i++) res *= f1[i + m][0]; return res; } mint2 solve(ll l, ll r) { if (l >= r - 1) return 1; mint2 res = 1; ll d = (r - l) / 2; res *= solve2(l, r - d, d); res *= solve(l, r - d); res *= solve(l + d, r); return res; } void solve() { } int main() { cin >> n; a.resize(n); for (ll i = 0; i < n; i++) cin >> a[i]; mint2 ans = 1; cout << solve(0, n).val(); return 0; }