Submit Info #12440

Problem Lang User Status Time Memory
$\sum_{i=0}^{\infty} r^i i^d$ cpp Bogdan AC 2543 ms 153.55 MiB

ケース詳細
Name Status Time Memory
0_00 AC 3 ms 0.68 MiB
0_01 AC 2 ms 0.68 MiB
0_02 AC 3 ms 0.68 MiB
2_00 AC 0 ms 0.67 MiB
2_01 AC 3 ms 0.68 MiB
2_02 AC 3 ms 0.80 MiB
2_03 AC 91 ms 8.29 MiB
2_04 AC 2543 ms 153.49 MiB
2_05 AC 2154 ms 153.55 MiB
example_00 AC 0 ms 0.67 MiB

#ifdef DEBUG #define _GLIBCXX_DEBUG #endif //#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; const int mod = 998244353; int mult(int a, int b) { return (1LL * a * b) % mod; } int sum(int a, int b) { int s = a + b; if (s >= mod) s -= mod; return s; } int sub(int a, int b) { int s = a - b; if (s < 0) s += mod; return s; } int pw(int a, ll b) { if (b == 0) return 1; if (b & 1) return mult(a, pw(a, b - 1)); int res = pw(a, b / 2); return mult(res, res); } //r^0 * f(0) + r^1 * f(1) + ... + r^(n - 1) * f(n - 1) = r^n * g(n) - g(0) // r^(n + 1) * g(n + 1) - r^n * g(n) = r^n * f(n) -> g(n + 1) = (g(n) + f(n)) / r // g(0) = c -> g(i) = const + g(0) / r^i // g(0), ... , g(d) -> sum(g(i) * coef_i) // r^0 + .. r^(n - 1) = (r^n / (r - 1) - 1 / (r - 1)) // r^0 + .. + r^i * i = ( // r^0 + .. + r^(n - 1) = (r^n - 1) / (r - 1) // g(n) = 1 / (r - 1), g(0) = 1 / (r - 1) // можно ускорить подсчет i^d решетом int solve(int d, int r) { if (r == 0) { return ((d == 0) ? 1 : 0); } vector < int > add(d + 2), coef(d + 2); add[0] = 0; coef[0] = 1; int invr = pw(r, mod - 2); for (int i = 0; i <= d; i++) { coef[i + 1] = mult(coef[i], invr); add[i + 1] = mult(invr, sum(pw(i, d), add[i])); } vector < int > inv(d + 2); inv[1] = 1; for (int i = 2; i <= d + 1; i++) { inv[i] = mult(inv[mod % i], mod - mod / i); } //calc_in_(d + 1) vector < int > invfact(d + 2); invfact[0] = 1; for (int i = 1; i <= d + 1; i++) { invfact[i] = mult(invfact[i - 1], inv[i]); } int tot_fact = 1; for (int i = 1; i <= d + 1; i++) tot_fact = mult(tot_fact, i); int tot_coef = 0; int tot_add = 0; for (int i = 0; i <= d + 1; i++) { int cnk = mult(tot_fact, mult(invfact[i], invfact[d + 1 - i])); if (i & 1) cnk = sub(0, cnk); tot_coef = sum(tot_coef, mult(cnk, coef[i])); tot_add = sum(tot_add, mult(cnk, add[i])); } int g0 = 0; if (tot_coef == 0) { assert(r == 1); g0 = 0; } else { g0 = mult(pw(tot_coef, mod - 2), sub(0, tot_add)); } assert(sum(mult(g0, tot_coef), tot_add) == 0); return sub(0, g0); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); int d, r; cin >> r >> d; cout << solve(d, r); return 0; }