1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
| #include <bits/stdc++.h> using namespace std;
#define Getmod
#ifdef Fread char buf[1 << 21], *iS, *iT; #define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) #define getchar gc #endif
template <typename T> void r1(T &x) { x = 0; char c(getchar()); int f(1); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48); x *= f; }
#ifdef Getmod const int mod = 998244353; template <int mod> struct typemod { int z; typemod(int a = 0) : z(a) {} inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);} inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);} inline int mul(int a,int b) const {return 1ll * a * b % mod;} typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));} typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));} typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));} typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;} typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;} typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;} int operator == (const typemod<mod> &x) const {return x.z == z;} int operator != (const typemod<mod> &x) const {return x.z != z;} }; typedef typemod<mod> Tm; #endif const Tm G = 3, invG = 332748118; template <typename T,typename... Args> inline void r1(T& t, Args&... args) { r1(t); r1(args...); }
const int maxn = 4e5 + 5; const int maxm = maxn << 1;
Tm tmp[maxn], Sl[maxn], Sr[maxn], fac[maxn], inv[maxn], C[maxn]; int rev[maxn]; int lim, len; void getrev(int x) { lim = 1, len = 0; while(lim <= x) lim <<= 1, ++ len; for(int i = 0; i < lim; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1)); }
Tm ksm(Tm x,int mi) { if(mi < 0) return 0; Tm res(1); while(mi) { if(mi & 1) res *= x; mi >>= 1; x *= x; } return res; }
void NTT(Tm *A,int opt = 1) { for(int i = 0; i < lim; ++ i) if(i < rev[i]) swap(A[i], A[rev[i]]); for(int mid = 1; mid < lim; mid <<= 1) { Tm wn(ksm((opt == 1) ? G : invG, (mod - 1) / (mid << 1))); for(int j = 0, c = (mid << 1); j < lim; j += c) { Tm W(1); for(int k = 0; k < mid; ++ k, W *= wn) { Tm x = A[j + k], y = W * A[j + k + mid]; A[j + k] = x + y; A[j + k + mid] = x - y; } } } if(opt != 1) { Tm z = ksm(lim, mod - 2); for(int i = 0; i < lim; ++ i) A[i] *= z; } }
int n, k;
signed main() {
int i, j; r1(n, k); Tm vis[2] = {1, mod - 1}; fac[0] = 1; for(i = 1; i <= k; ++ i) fac[i] = fac[i - 1] * i; inv[k] = ksm(fac[k], mod - 2); for(i = k - 1; ~ i; -- i) inv[i] = inv[i + 1] * (i + 1); for(i = 0; i <= k; ++ i) { Sl[i] = inv[i] * vis[i & 1]; Sr[i] = ksm(i, k) * inv[i]; } getrev(2 * k);
NTT(Sl, 1), NTT(Sr, 1); for(i = 0; i < lim; ++ i) Sl[i] *= Sr[i]; NTT(Sl, -1);
Sl[0] = 0; C[0] = 1; for(i = 1; i <= k; ++ i) C[i] = C[i - 1] * (n - i + 1) * ksm(i, mod - 2);
Tm ans(0); for(i = 0; i <= k; ++ i) ans += C[i] * Sl[i] * fac[i] * ksm(n + 1, n - i); printf("%d\n", ans.z); return 0; }
|