|
| 1 | +// @brief $\sum\limits_{i=0}^\infty r^i i^d$ |
| 2 | +#definePROBLEM"https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial_limit" |
| 3 | +#pragma GCC optimize("Ofast,unroll-loops") |
| 4 | +#defineCP_ALGO_MAXN1 <<24 |
| 5 | +#include"cp-algo/math/poly.hpp" |
| 6 | +#include<bits/stdc++.h> |
| 7 | + |
| 8 | +usingnamespacestd; |
| 9 | +usingnamespacecp_algo::math; |
| 10 | + |
| 11 | +constint mod =998244353; |
| 12 | +typedef modint<mod> base; |
| 13 | +typedefpoly_t<base> polyn; |
| 14 | + |
| 15 | +basenCr(int n,int r) { |
| 16 | +return fact<base>(n) * rfact<base>(r) * rfact<base>(n-r); |
| 17 | +} |
| 18 | + |
| 19 | +polynxm1k(size_t k) { |
| 20 | + polyn::Vectorans(k+1); |
| 21 | +for(int i =0; i <= k; i++) { |
| 22 | + ans[i] = (k - i) &1 ? -nCr(k, i) :nCr(k, i); |
| 23 | + } |
| 24 | +return ans; |
| 25 | +} |
| 26 | + |
| 27 | +voidsolve() { |
| 28 | +int r, d; |
| 29 | + cin >> r >> d; |
| 30 | + polyn num =polyn(bpow(base(1-r), d+1)) -bpow(base(r), d+1) *xm1k(d+1); |
| 31 | + polyn den =polyn(bpow(base(1-r), d+2)) -bpow(base(1-r), d+1) * r * (polyn::xk(1) -polyn(base(1))); |
| 32 | + polyn H = num / den; |
| 33 | + base ans =0; |
| 34 | + |
| 35 | + base id[d+1]; |
| 36 | + vector<int>lp(d+1); |
| 37 | + id[0] =bpow(base(0), d); |
| 38 | + id[1] =1; |
| 39 | +for(int i =2; i <= d; i++) { |
| 40 | +if(lp[i] ==0) { |
| 41 | + id[i] =bpow(base(i), d); |
| 42 | +for(int j = i; j <= d; j += i) { |
| 43 | + lp[j] = i; |
| 44 | + } |
| 45 | + }else { |
| 46 | + id[i] = id[lp[i]] * id[i / lp[i]]; |
| 47 | + } |
| 48 | + } |
| 49 | + |
| 50 | +for(int i =0; i <= d; i++) { |
| 51 | + ans += H[i] * id[i]; |
| 52 | + } |
| 53 | + cout << ans << endl; |
| 54 | +} |
| 55 | + |
| 56 | +signedmain() { |
| 57 | +//freopen("input.txt", "r", stdin); |
| 58 | +ios::sync_with_stdio(0); |
| 59 | + cin.tie(0); |
| 60 | +int t; |
| 61 | + t =1;// cin >> t; |
| 62 | +while(t--) { |
| 63 | +solve(); |
| 64 | + } |
| 65 | +} |