萌新求助卡常
查看原帖
萌新求助卡常
362750
TernaryTree楼主2024/4/11 14:06
#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define gc getchar
#define pc putchar

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

const int maxn = (1 << 20) + 10;
const int mod = 0x3b800001, groot = 3;
const bool multidata = 0;

int read() {
	int x = 0, f = 1; char c = gc();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = gc(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
	return x * f;
}

void write(int x) {
	if (x < 0) pc('-'), x = -x;
	if (x < 10) return void (pc(x + '0'));
	write(x / 10), pc(x % 10 + '0');
}

int n, k;
int a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], f[maxn], g[maxn], h[maxn];
int omg[maxn], inv[maxn], rev[maxn];

int power(int a, int b, int p = mod) {
	int t = 1;
	a %= p;
	while (b) {
		if (b & 1) t = t * a % p;
		a = a * a % p, b >>= 1;
	}
	return t;
}

void getrev(int n) {
	rev[0] = 0;
	rep(i, 1, n - 1) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? (n >> 1) : 0);
}

void getw(int n) {
	int x = power(groot, (mod - 1) / n), y = power(x, mod - 2);
	omg[0] = inv[0] = 1;
	rep(i, 1, n - 1) {
		omg[i] = omg[i - 1] * x % mod;
		inv[i] = inv[i - 1] * y % mod;
	}
}

void ntt(int * a, int n, int * w) {
	rep(i, 0, n - 1) if (rev[i] < i) swap(a[rev[i]], a[i]);
	for (int len = 2; len <= n; len <<= 1) {
		int m = len >> 1;
		for (int i = 0; i < n; i += len) {
			rep(j, 0, m - 1) {
				int x = w[n / len * j], y = x * a[i + j + m] % mod;
				a[i + j + m] = (a[i + j] - y + mod) % mod;
				a[i + j] = (a[i + j] + y) % mod;
			}
		}
	}
}

int tmpa[maxn], tmpb[maxn], tmpc[maxn], tmpd[maxn], tmpe[maxn], tmpf[maxn], tmpg[maxn];

void Mul(int * a, int * b, int * c, int n, int m) {
	rep(i, 0, n - 1) tmpa[i] = a[i];
	rep(i, 0, m - 1) tmpb[i] = b[i];
	int lim = 1;
	while (lim <= n + m - 1) lim <<= 1;
	rep(i, n, lim - 1) tmpa[i] = 0;
	rep(i, m, lim - 1) tmpb[i] = 0;
	getrev(lim), getw(lim);
	ntt(tmpa, lim, omg), ntt(tmpb, lim, omg);
	rep(i, 0, lim - 1) c[i] = tmpa[i] * tmpb[i] % mod;
	ntt(c, lim, inv);
	int pw = power(lim, mod - 2);
	rep(i, 0, lim - 1) c[i] = c[i] * pw % mod;
	rep(i, n + m - 1, lim - 1) c[i] = 0;
} // tmpa, tmpb

void Inv(int * a, int * b, int n) {
	if (n == 1) return void (b[0] = power(a[0], mod - 2));
	int m = (n + 1) >> 1;
	Inv(a, b, m);
	for (int i = 0; i < n; i++) tmpa[i] = a[i];
	for (int i = n; i < maxn; i++) tmpa[i] = 0;
	for (int i = 0; i < m; i++) tmpb[i] = b[i];
	for (int i = m; i < maxn; i++) tmpb[i] = 0;
	int lim = 1;
	while (lim <= n * 2) lim <<= 1;
	getrev(lim), getw(lim);
	ntt(tmpa, lim, omg), ntt(tmpb, lim, omg);
	for (int i = 0; i < lim; i++) b[i] = (tmpb[i] * 2 % mod - tmpa[i] % mod * tmpb[i] % mod * tmpb[i] % mod + mod) % mod;
	ntt(b, lim, inv);
	int pw = power(lim, mod - 2);
	for (int i = 0; i < n; i++) b[i] = b[i] * pw % mod;
	for (int i = n; i < lim; i++) b[i] = 0;
} // tmpa, tmpb

void Deriv(int * a, int n) {
	rep(i, 0, n - 2) a[i] = a[i + 1] * (i + 1) % mod;
	a[n - 1] = 0;
}

void Integ(int * a, int n) {
	per(i, n - 1, 1) a[i] = a[i - 1] * power(i, mod - 2) % mod;
	a[0] = 0;
}

void Ln(int * a, int * b, int n) {
	rep(i, 0, n - 1) tmpd[i] = a[i];
	Inv(tmpd, tmpc, n);
	Deriv(tmpd, n);
	Mul(tmpd, tmpc, b, n, n);
	Integ(b, n);
	rep(i, n, maxn - 1) b[i] = 0;
}

void Exp(int * a, int * b, int n) {
	if (n == 1) return void (b[0] = 1);
	Exp(a, b, (n + 1) >> 1);
	rep(i, 0, n - 1) tmpe[i] = 0;
	Ln(b, tmpe, n);
	rep(i, 0, n - 1) tmpe[i] = (a[i] - tmpe[i] + mod) % mod;
	++tmpe[0];
	Mul(b, tmpe, tmpf, n, n);
	rep(i, n, maxn - 1) tmpf[i] = 0;
	rep(i, 0, n - 1) b[i] = tmpf[i];
} // tmpa, tmpb, tmpc, tmpd, tmpe, tmpf

int fac[maxn], ifac[maxn];

void init() {
	fac[0] = 1; rep(i, 1, maxn - 1) fac[i] = fac[i - 1] * i % mod;
	ifac[maxn - 1] = power(fac[maxn - 1], mod - 2); per(i, maxn - 2, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}

void fake_main() {
	init();
	k = read(), n = read();
	f[0] = k + 1; rep(i, 1, n) f[i] = (k + 1) * f[i - 1] % mod;
	rep(i, 0, n) f[i] = f[i] * ifac[i + 1] % mod, g[i] = ifac[i + 1];
	Inv(g, h, n + 1);
	Mul(f, h, d, n + 1, n + 1);
	rep(i, 1, n) {
		a[i] = d[i] * fac[i - 1] % mod;
		if (!(i & 1)) a[i] = mod - a[i];
	}
	Exp(a, b, n + 1);
	rep(i, 1, n) write(b[i] * fac[i] % mod), pc('\n');
}

signed main() {
	int T = multidata ? read() : 1;
	while (T--) fake_main();
	return 0;
}

2024/4/11 14:06
加载中...