結果
問題 | No.2580 Hyperinflation |
ユーザー |
![]() |
提出日時 | 2023-12-08 18:23:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#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^-1int 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' Pint 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';}