結果
問題 | No.2513 Power Eraser |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-16 12:19:46 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,700 ms / 6,000 ms |
コード長 | 1,867 bytes |
コンパイル時間 | 3,424 ms |
コンパイル使用メモリ | 144,772 KB |
実行使用メモリ | 54,524 KB |
最終ジャッジ日時 | 2024-09-20 17:00:37 |
合計ジャッジ時間 | 54,264 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#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; while (t < mod) { t *= 2; 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); 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; }