第二类斯特林数·行

题目描述

输出 $\begin{Bmatrix} n \\0 \end{Bmatrix},\begin{Bmatrix} n \\1 \end{Bmatrix},\begin{Bmatrix} n \\2 \end{Bmatrix},\dots,\begin{Bmatrix} n \\n \end{Bmatrix}$ 的值。

$1\leqslant n\leqslant 2\times 10^5$ 。

题解

从组合意义出发考虑，容斥，

$$\begin{aligned} m!\begin{Bmatrix} n \\m\end{Bmatrix}&=\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n\\ m!\begin{Bmatrix} n \\m\end{Bmatrix}&=m!\sum_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\times\dfrac{i^n}{i!}\\ \begin{Bmatrix} n \\m\end{Bmatrix}&=\sum_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\times\dfrac{i^n}{i!} \end{aligned}$$

卷积形式，NTT 即可。

代码

const int N = 2e5 + 10, mod = 167772161, G = 3, invG = 55924054;
const int pN = N << 3;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	#define clr(f, x) memset(f, 0, sizeof(int) * (x))
	#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
	int add (int x, int y) { return x + y > mod? x + y - mod: x + y; }
	int dec (int x, int y) { return x - y < 0? x - y + mod: x - y; }
	int mul (int x, int y) { return 1ll * x * y % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int n;
	struct poly {
		int tr[pN];

		void init(int n, int siz) {
			for (int i = 0; i < n; ++i)
				tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
		}

		void NTT(int *f, int n, int op = 1) {
			for (int i = 0; i < n; i++)
				if (i < tr[i]) swap(f[i], f[tr[i]]);
			for (int p = 1; p < n; p <<= 1) {
				int omega = qpow(op? G: invG, (mod - 1) / (p << 1));
				for (int j = 0; j <	n; j += p << 1) 
					for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
						int x = f[j | k], y = mul(w, f[j | p | k]);
						f[j | k] = add(x, y), f[j | p | k] = dec(x, y);
					}
			}
			if (!op) {
				int invn = qpow(n, mod - 2);
				for (int i = 0; i < n; i++) f[i] = mul(f[i], invn);
			}
		}
		void times (int *f, int *g, int n, int m, int T) {
			int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
			init(lim, lsiz);
			static int tmp[pN]; clr(f + n, lim - n), cpy (tmp, g, m), clr(tmp + m, lim - m);
			NTT(f, lim), NTT(tmp, lim);
			for (int i = 0; i < lim; i++) f[i] = mul(f[i], tmp[i]);
			NTT(f, lim, 0);
			clr (f + T, lim - 1), clr (tmp, lim);
		}
	} p;
	int S[N], f[pN], g[pN];
	int fac[N], inv[N], invs[N];
	void getS() {
		fac[0] = 1;	for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
		inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mod % i], mod - mod / i);
		invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = mul(invs[i - 1], inv[i]);
		for (int i = 0; i <= n; i++) {
			f[i] = mul((i & 1)? mod - 1: 1, invs[i]);
			g[i] = mul(qpow(i, n), invs[i]);
		}
		p.times(f, g, n + 1, n + 1, n + 1);
		for (int i = 0; i <= n; i++) S[i] = f[i];
	}
	int main () {
		n = Read();
		getS();
		for (int i = 0; i <= n; i++) printf ("%d ", S[i]); putchar(10);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}