萌新求助 * 2
  • 板块学术版
  • 楼主Mr_Wu
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/5/7 10:51
  • 上次更新2023/11/7 02:58:45
查看原帖
萌新求助 * 2
62308
Mr_Wu楼主2020/5/7 10:51

P5850 calc 加强版 这题,我的板子常数太大了,全 tle,有人能帮帮忙嘛?谢谢!

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ri register int

const int MAXN = 2000005, MOD = 998244353, Gen = 3;

ll q_pow(ll a, ll b, ll p = MOD) {
	ll ret = 1;
	for (; b; a = a * a % p, b >>= 1) if (b & 1) ret = ret * a % p;
	return ret;
}
ll inv(ll x, ll p = MOD) { return q_pow(x, p - 2, p); }

int rev[21][MAXN], fac[MAXN], ifac[MAXN], I[MAXN], Wn[MAXN], iWn[MAXN];
ll tntt[MAXN];
void NTT(int* A, int LIM, int L, int op) {
	for (ri i = 0; i < LIM; ++i) tntt[i] = A[i];
	for (ri i = 0; i < LIM; ++i) if (i < rev[L][i]) swap(tntt[i], tntt[rev[L][i]]);
	for (ri l = 2, t = 1; l <= LIM; l <<= 1, ++t) {
		ll g = op == -1 ? iWn[t] : Wn[t];
		for (ri i = 0; i < LIM; i += l) {
			ll w = 1;
			for (ri j = i; j < (i | (l >> 1)); ++j, w = w * g % MOD) {
				int x = tntt[j], y = w * tntt[j | (l >> 1)] % MOD;
				tntt[j] = (x + y) % MOD, tntt[j | (l >> 1)] = (x - y) % MOD;
			}
		}
	}
	if (op == -1) {
		int invLIM = inv(LIM);
		for (ri i = 0; i < LIM; ++i) tntt[i] = tntt[i] * invLIM % MOD;
	}
	for (ri i = 0; i < LIM; ++i) A[i] = tntt[i];
}
void Multiply(int* A, int* B, int LIM, int L) {
	NTT(A, LIM, L, 1), NTT(B, LIM, L, 1);
	for (ri i = 0; i < LIM; ++i) A[i] = 1ll * A[i] * B[i] % MOD;
	NTT(A, LIM, L, -1);
}

int Tinv[MAXN];
void Inverse(const int* F, int* G, int LIM, int L) {
	G[0] = inv(F[0]);
	for (int lim = 2, l = 1; lim <= LIM; lim <<= 1, ++l) {
		for (ri i = 0; i < lim; ++i) Tinv[i] = F[i];
		for (ri i = lim; i < (lim << 1); ++i) Tinv[i] = 0;
		NTT(Tinv, lim << 1, l + 1, 1), NTT(G, lim << 1, l + 1, 1);
		for (ri i = 0; i < (lim << 1); ++i) G[i] = (2 * G[i] - 1ll * Tinv[i] * G[i] % MOD * G[i]) % MOD;
		NTT(G, lim << 1, l + 1, -1);
		for (ri i = lim; i < (lim << 1); ++i) G[i] = 0;
	}
}
void Derivative(int* F, int LIM) {
	for (ri i = 0; i < LIM - 1; ++i) F[i] = 1ll * F[i + 1] * (i + 1) % MOD;
	F[LIM - 1] = 0;
}
void Inter(int* F, int LIM) {
	for (ri i = LIM - 1; i >= 1; --i) F[i] = 1ll * F[i - 1] * I[i] % MOD;
	F[0] = 0;
}
int Tln[MAXN];
void Ln(int* F, int LIM, int L) {
	Inverse(F, Tln, LIM, L);
	Derivative(F, LIM);
	Multiply(F, Tln, LIM << 1, L + 1);
	Inter(F, LIM);
	for (ri i = 0; i < (LIM << 1); ++i) Tln[i] = 0;
}

int Texp[MAXN];
void Exp(const int* F, int* G, int LIM, int L) {
	G[0] = 1;
	for (int lim = 2, l = 1; lim <= LIM; lim <<= 1, ++l) {
		for (ri i = 0; i < lim; ++i) Texp[i] = G[i];
		for (ri i = lim; i < (lim << 1); ++i) Texp[i] = 0;
		Ln(G, lim, l);
		for (ri i = 0; i < lim; ++i) G[i] = (-G[i] + F[i]) % MOD;
		++G[0];
		Multiply(G, Texp, lim << 1, l + 1);
		for (ri i = lim; i < (lim << 1); ++i) G[i] = 0;
	}
}

int K, N, LIM = 1, L, F[MAXN], G[MAXN], H[MAXN];
int main() {
	scanf("%d%d", &K, &N);
	Wn[0] = iWn[0] = 1;

	while (LIM <= N + 1) {
		LIM <<= 1, ++L, Wn[L] = q_pow(Gen, (MOD - 1) / LIM), iWn[L] = inv(Wn[L]);
		for (ri i = 0; i < LIM; ++i) rev[L][i] = (rev[L][i >> 1] >> 1) | ((i & 1) << (L - 1));
	}
	LIM <<= 1, ++L, Wn[L] = q_pow(Gen, (MOD - 1) / LIM), iWn[L] = inv(Wn[L]);
	for (ri i = 0; i < LIM; ++i) rev[L][i] = (rev[L][i >> 1] >> 1) | ((i & 1) << (L - 1));
	LIM >>= 1, --L;

	fac[0] = ifac[0] = fac[1] = ifac[1] = I[1] = 1;
	for (ri i = 2; i <= LIM; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % MOD, I[i] = -1ll * (MOD / i) * I[MOD % i] % MOD, ifac[i] = 1ll * ifac[i - 1] * I[i] % MOD;
	}
	F[1] = K + 1;
	Exp(F, G, LIM, L);
	for (ri i = 0; i < LIM; ++i) G[i] = (G[i + 1] - ifac[i + 1]) % MOD;
	for (ri i = 0; i < LIM; ++i) F[i] = ifac[i + 1];
	Inverse(F, H, LIM, L);
	Multiply(G, H, LIM << 1, L + 1);
	for (ri i = LIM; i < (LIM << 1); ++i) G[i] = 0;
	G[0] = 0;
	for (ri i = 1; i < LIM; ++i) G[i] = 1ll * (i & 1 ? 1 : -1) * G[i] * fac[i] % MOD * I[i] % MOD;
	for (ri i = 0; i < LIM; ++i) F[i] = 0;
	Exp(G, F, LIM, L);
	for (ri i = 1; i <= N; ++i) printf("%d\n", (1ll * fac[i] * F[i] % MOD + MOD) % MOD);
	return 0;
}
2020/5/7 10:51
加载中...