結果
問題 | No.2580 Hyperinflation |
ユーザー |
![]() |
提出日時 | 2023-12-08 18:23:09 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,901 ms / 4,000 ms |
コード長 | 5,295 bytes |
コンパイル時間 | 3,897 ms |
コンパイル使用メモリ | 297,148 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-27 02:55:26 |
合計ジャッジ時間 | 37,037 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 4 ms
5,376 KB |
testcase_14 | AC | 8 ms
5,376 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 5 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 181 ms
5,376 KB |
testcase_19 | AC | 178 ms
5,376 KB |
testcase_20 | AC | 178 ms
5,376 KB |
testcase_21 | AC | 178 ms
5,376 KB |
testcase_22 | AC | 178 ms
5,376 KB |
testcase_23 | AC | 2,819 ms
5,376 KB |
testcase_24 | AC | 2,856 ms
5,376 KB |
testcase_25 | AC | 2,868 ms
5,376 KB |
testcase_26 | AC | 2,896 ms
5,376 KB |
testcase_27 | AC | 2,866 ms
5,376 KB |
testcase_28 | AC | 2,901 ms
5,376 KB |
testcase_29 | AC | 2,891 ms
5,376 KB |
testcase_30 | AC | 2,892 ms
5,376 KB |
testcase_31 | AC | 2,858 ms
5,376 KB |
testcase_32 | AC | 2,714 ms
5,376 KB |
testcase_33 | AC | 2,705 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; using mint = modint998244353; constexpr int FACT_SIZE = 3000; mint Fact[FACT_SIZE + 1]; mint iFact[FACT_SIZE + 1]; mint inv[FACT_SIZE + 1]; const auto fact_init = [] { Fact[0] = mint::raw(1); for(int i = 1; i <= FACT_SIZE; ++i) { Fact[i] = Fact[i-1] * i; } iFact[FACT_SIZE] = Fact[FACT_SIZE].inv(); for(int i = FACT_SIZE; i; --i) { iFact[i-1] = iFact[i] * i; } for (int i = 1; i <= FACT_SIZE; i++) { inv[i] = iFact[i] * Fact[i-1]; } return false; }(); vector<mint> prod[4096]; void set_prod(int i) { assert(0 <= i && i < 2048); const mint im = i; int p = 2048 + i; while (p > 0) { auto& f = prod[p]; f.emplace_back(0); rrep(j, ssize(f) - 1) f[j+1] -= im * f[j]; p >>= 1; } } vector<mint> get_prod(int l, int r) { int len = bit_ceil(1U * (r - l)); r = l + len; assert(((len - 1) & l) == 0); int p = (2048 + l) / len; assert(p > 0); return prod[p]; } vector<mint> fps_inverse(vector<mint> f, int precision) { int n = f.size(); assert(n >= 1 && f[0] != 0); int len = 1; const int z = bit_ceil(1U * precision); vector<mint> g{f[0].inv()}; const mint inv4 = mint(4).inv(); mint inv4k = 1; while (len < z) { int nlen = 2 * len; vector<mint> ft(f.begin(), f.begin() + min(n, nlen)); ft.resize(nlen); butterfly(ft); vector<mint> gt = g; gt.resize(nlen); internal::butterfly(gt); for (int i = 0; i < nlen; i++) ft[i] *= gt[i]; internal::butterfly_inv(ft); for (int i = 0; i < len; i++) ft[i] = mint(); internal::butterfly(ft); for (int i = 0; i < nlen; i++) ft[i] *= gt[i]; internal::butterfly_inv(ft); inv4k *= inv4; mint c = -inv4k; for (int i = len; i < nlen; i++) g.emplace_back(c * ft[i]); len = nlen; } g.resize(precision); return g; } vector<mint> monomial2factorial(vector<mint> f) { // a x = a P^-1 P x = a' P x // a' = a P^-1 int n = f.size(); if (n == 0) return f; ranges::reverse(f); f = convolution(f, fps_inverse(prod[1], n)); f.resize(n); auto dfs2 = [&](auto&& self, int l, int r) { if (r - l == 1) return; int c = l + bit_ceil(1U * (r - l)) / 2; auto g = convolution(vector<mint>(f.begin() + n - r, f.begin() + n - l), get_prod(c, r)); copy(g.begin() + r - c, g.begin() + r - l, f.begin() + n - c); self(self, l, c); self(self, c, r); }; dfs2(dfs2, 0, n); ranges::reverse(f); return f; } vector<mint> factorial2monomial(vector<mint> f) { // a x = a P^-1 P x = a' P x // a = a' P int n = f.size(); auto dfs = [&](auto&& self, int l, int r) { if (r - l == 1) return; int c = l + bit_ceil(1U * (r - l)) / 2; self(self, l, c); self(self, c, r); int p = [&](int l, int r) { int len = bit_ceil(1U * (r - l)); r = l + len; assert(((len - 1) & l) == 0); return (2048 + l) / len; }(l, c); assert(p > 0); ranges::reverse(prod[p]); auto g = convolution(vector<mint>(f.begin() + c, f.begin() + r), prod[p]); ranges::reverse(prod[p]); for (int i = l; i < c; i++) f[i] += g[i - l]; for (int i = c; i < r; i++) f[i] = g[i - l]; return; }; dfs(dfs, 0, n); return f; } vector<mint> Taylor_shift(vector<mint> f, mint c) { int n = f.size(); for (int i = 0; i < n; i++) { f[i] *= Fact[i]; } vector<mint> g(n); mint pow_c = 1; for (int i = 0; i < n; i++) { g[n - 1 - i] = pow_c * iFact[i]; pow_c *= c; } vector<mint> h = convolution(f, g); h.erase(h.begin(), h.end() - n); for (int i = 0; i < n; i++) { h[i] *= iFact[i]; } return h; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; VI a(n); rep(i, n - 1) cin >> a[i]; string m; cin >> m; for (char& c : m) c -= '0'; vector<mint> c(n); rep(i, n - 1) { unsigned int now = 0; rep(j, ssize(m)) { now = 10 * now + m[j]; m[j] = now / a[i]; now %= a[i]; } c[i] = now; } { mint now; for (char c : m) now = 10 * now + c; c[n - 1] = now; } rep(k, 12) for (int i = 1 << k; i < 1 << (k + 1); i++) prod[i].reserve((1 << (11 - k)) + 1); rep(i, 4096) prod[i] = {1}; vector<mint> f{1}; set_prod(0); for (int i = 1; i < n; i++) { f = monomial2factorial(move(f)); f.insert(f.begin(), mint()); for (int j = 1; j <= i; j++) f[j] *= inv[j]; set_prod(i); f = factorial2monomial(move(f)); f = Taylor_shift(move(f), 1 + c[i]); mint aj = 1; rep(j, i + 1) { f[j] *= aj; aj *= a[i]; } } cout << f[0].val() << '\n'; }