結果
問題 | No.2688 Cell Proliferation (Hard) |
ユーザー | shobonvip |
提出日時 | 2024-03-20 23:07:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 776 ms / 4,000 ms |
コード長 | 2,442 bytes |
コンパイル時間 | 4,724 ms |
コンパイル使用メモリ | 274,124 KB |
実行使用メモリ | 39,344 KB |
最終ジャッジ日時 | 2024-03-20 23:08:13 |
合計ジャッジ時間 | 19,165 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 74 ms
7,136 KB |
testcase_04 | AC | 747 ms
37,920 KB |
testcase_05 | AC | 361 ms
21,840 KB |
testcase_06 | AC | 172 ms
12,208 KB |
testcase_07 | AC | 170 ms
12,136 KB |
testcase_08 | AC | 699 ms
37,260 KB |
testcase_09 | AC | 655 ms
33,996 KB |
testcase_10 | AC | 744 ms
38,496 KB |
testcase_11 | AC | 707 ms
37,560 KB |
testcase_12 | AC | 195 ms
12,700 KB |
testcase_13 | AC | 772 ms
39,336 KB |
testcase_14 | AC | 630 ms
32,680 KB |
testcase_15 | AC | 776 ms
39,344 KB |
testcase_16 | AC | 605 ms
32,268 KB |
testcase_17 | AC | 412 ms
22,488 KB |
testcase_18 | AC | 734 ms
38,640 KB |
testcase_19 | AC | 393 ms
22,548 KB |
testcase_20 | AC | 297 ms
18,088 KB |
testcase_21 | AC | 302 ms
18,060 KB |
testcase_22 | AC | 377 ms
22,284 KB |
testcase_23 | AC | 315 ms
18,676 KB |
testcase_24 | AC | 725 ms
38,352 KB |
testcase_25 | AC | 193 ms
12,772 KB |
testcase_26 | AC | 775 ms
38,808 KB |
testcase_27 | AC | 390 ms
22,632 KB |
testcase_28 | AC | 624 ms
32,360 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; //* ATCODER #include<atcoder/all> using namespace atcoder; typedef modint998244353 mint; //*/ /* BOOST MULTIPRECISION #include<boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template <typename T> T max(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template <typename T> T min(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template <typename T> T sum(vector<T> &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } vector<mint> poly_inv(vector<mint> &a, int M = -314159265){ if (M == -314159265) M = (int)a.size(); else if (M <= 0) return {}; int n = a.size(); mint r = a[0].pow((ll)(mint::mod())-2); int m = 1; vector<mint> res = {r}; while (m < M){ vector<mint> f = a; f.resize(2 * m); vector<mint> g = res; g.resize(2 * m); internal::butterfly(f); internal::butterfly(g); for (int i=0; i<2*m; i++){ f[i] = f[i] * g[i]; } internal::butterfly_inv(f); for (int i=0; i<m; i++){ f[i] = f[i + m]; } for (int i=0; i<m; i++){ f[i + m] = 0; } internal::butterfly(f); for (int i=0; i<2*m; i++){ f[i] = f[i] * g[i]; } internal::butterfly_inv(f); mint iz = mint(2*m).inv(); iz = -iz * iz; for (int i=0; i<m; i++){ f[i] = f[i] * iz; } res.insert(res.end(), f.begin(), f.begin()+m); m <<= 1; } res.resize(M); return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int p1, p2, q1, q2, t; cin >> p1 >> p2 >> q1 >> q2 >> t; mint p = mint(p1) / mint(p2); mint q = mint(q1) / mint(q2); vector<mint> C(t+1); rep(i,0,t+1){ C[i] = p * mint(q).pow(ll(i)*(i+1)/2); } vector<mint> D(t+1); D[0] = 1; rep(i,0,t){ D[i+1] = - C[i]; } vector<mint> B = convolution(C, poly_inv(D)); B.resize(t); mint ans = mint(q).pow(ll(t)*(t+1)/2); rep(i,0,t){ ans += B[i] * mint(q).pow(ll(t-i)*(t-i-1)/2); } cout << ans.val() << '\n'; }