求助,过不了第四个样例
查看原帖
求助,过不了第四个样例
1042069
ThroughBall楼主2024/5/24 18:16
#include <iostream>
#define MAXN 10000000
using namespace std;

const int MOD = 998244353;
int n, k, fac[MAXN + 5], inv[MAXN + 5], f[MAXN + 5], sumf; 

int exp(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n % 2 == 0) { res = res * a % MOD; }
		a = a * a % MOD;
		n /= 2;
	}
	return res;
}

void init() {
	fac[0] = inv[0] = 1;
	for (int i = 1; i <= MAXN; ++i) { fac[i] = fac[i - 1] * i % MOD; }
	inv[n] = exp(fac[MAXN], MOD - 2);
	for (int i = n - 1; i >= 1; --i) { inv[i] = inv[i + 1] * (i + 1) % MOD; }
}

int main() {
	init();
	cin >> n >> k;
	for (int i = 1; i <= k; ++i) { f[i] = fac[i]; } 
	sumf = k;
	for (int i = k + 1; i <= n; ++i) {
		f[i] = sumf * fac[i - 1] % MOD;
		sumf = (sumf - f[i - k] * inv[i - k] % MOD + f[i] * inv[i] % MOD) % MOD;
	}
	cout << f[n] << endl;
	return 0;
}

RT,第四个样例过不了,但是看了好多遍没看到问题

2024/5/24 18:16
加载中...