记录编号	532930	评测结果	AAAAAAAAAA
题目名称	2340.[HZOI 2015]疯狂的求和问题	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2019-06-08 18:42:00	内存使用	12.03 MiB

#define _CRT_SECURE_NO_WARNINGS
#define maxn 500010ul

#include <stdio.h>

int n, k, s1, P[maxn], invf[maxn], fac[maxn], inv[maxn]; const int mod = 998244353;

void read(register int& x) {
	x = 0; register int c = getchar(); for (; c<'0' || c>'9'; c = getchar());
	for (; c >= '0' && c <= '9'; c = getchar()) x = ((x * 10ll) + (c ^ 48ll)) % mod; return;
}

int power(int p, int k) {
	if (p == -1) { if (k & 1) return -1; else return 1; }
	int ret = 1;
	while (k) {
		if (k & 1) ret = 1ll * ret * p % mod;
		k >>= 1, p = 1ll * p * p % mod;
	} return ret;
}

int main() {
	freopen("Crazy_Sum.in", "r", stdin);
	freopen("Crazy_Sum.out", "w", stdout);
	read(n), read(k), n++, k++; fac[0] = inv[0] = inv[1] = invf[0] = 1;
	for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	for (int i = 2; i <= k; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 1; i <= k; i++) invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
	for (int i = 2; i <= k; i++) P[i] = (power(i - 1, k - 1) + P[i - 1]) % mod;
	if (n <= k) return printf("%d\n", P[n]), 0;
	s1 = n; for (int i = 1; i <= k; i++) s1 = 1ll * s1 * (n - i) % mod;
	int ans = 0;
	for (int j = 0; j <= k; j++) (ans += 1ll * power(-1, k - j) * P[j] % mod * s1 % mod * invf[k - j] % mod * invf[j] % mod * power(n - j, mod - 2) % mod) %= mod;
	printf("%d\n", (ans % mod + mod) % mod); return 0;
}
/*
#include<stdio.h>
#define maxn 500010
#define mod 998244353
int n, k, s1, P[maxn], invfac[maxn], fac[maxn], inv[maxn];

int mypow(int x, int y) {
	if (x == -1)return y & 1 ? -1 : 1;
	int res = 1;
	while (y) {
		if (y & 1)res = 1ll*res * x % mod;
		y >>= 1;
		x = 1ll * x * x % mod;
	}
	return res;
}

int main() {
	freopen("Crazy_Sum.in", "r", stdin);
	freopen("Crazy_Sum.out", "w", stdout);
	scanf("%d%d", &n, &k);
	
	fac[0] = 1;
	for (int i = 1; i <= k + 1; ++i)
		fac[i] = 1ll * fac[i - 1] * i % mod;

	inv[1] = 1;
	for (int i = 2; i <= k + 1; ++i)
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

	invfac[0] = 1;
	for (int i = 1; i <= k + 1; ++i)
		invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;

	P[0] = 0;
	for (int i = 1; i <= k + 1; ++i)
		P[i] = (P[i - 1] + mypow(i, k)) % mod;

	if (n <= k + 1) {
		printf("%d\n", P[n]);
		return 0;
	}

	int s1 = 1;
	for (int i = n; i >= n - k - 1; --i)
		s1 = 1ll * s1 * i % mod;
	int ans = 0;
	for (int i = 0; i <= k + 1; ++i) {
		int temp = 1ll * s1 * invfac[i] % mod * invfac[k + 1 - i] % mod * mypow(n - i, mod - 2) % mod * mypow(-1, k + 1 - i);
		ans = (ans + 1ll * P[i] * temp) % mod;
	}
	printf("%d\n", (ans % mod + mod) % mod);
}
*/