【Bzoj4555】【Luogu P4091】求和（NTT）

题面

题解

先来颓柿子

$$ \sum_{i=0}^n\sum_{j=0}^iS(i,j)2^jj! \\ =\sum_{j=0}^n2^jj!\sum_{i=0}^nS(i,j) \\ \because S(n, m)=\frac1{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n=\sum_{i=0}^m\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!} \\ \therefore=\sum_{j=0}^n2^jj!\sum_{i=0}^n\sum_{k=0}^{j}\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!} \\ =\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!} \\ =\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!} $$

然后后面那一大坨可以看做卷积，因为要取模，$NTT$就好了。

#include <cstdio>

#include <algorithm>

using std::swap;

const int N = 2.7e5 + 10, Mod = 998244353, g = 3;

int n, m, P, jc[N], pow2[N], invjc[N];

int a[N], b[N], r[N], ret;

int qpow(int a, int b) {

	int ret = 1;

	while(b) {

		if(b & 1) ret = 1ll * ret * a % Mod;

		a = 1ll * a * a % Mod, b >>= 1;

	} return ret;

}

void NTT (int f[], int opt) {

	for(int i = 0; i < n; ++i) if(i < r[i]) swap(f[i], f[r[i]]);

	for(int len = 1, nl = 2; len < n; len = nl, nl <<= 1) {

		int rot = qpow(g, (Mod - 1) / nl);

		if(opt == -1) rot = qpow(rot, Mod - 2);

		for(int l = 0; l < n; l += nl) {

			int w = 1, r = l + len;

			for(int k = l; k < r; ++k, w = 1ll * w * rot % Mod) {

				int x = f[k], y = 1ll * f[k + len] * w % Mod;

				f[k] = (x + y) % Mod, f[k + len] = (x + Mod - y) % Mod;

			}

		}

	}

}

int main () {

	scanf("%d", &n), jc[0] = pow2[0] = invjc[0] = b[0] = 1, b[1] = n + 1;

	for(int i = 1; i <= n; ++i)

		jc[i] = 1ll * jc[i - 1] * i % Mod, pow2[i] = (pow2[i - 1] << 1) % Mod;

	invjc[n] = qpow(jc[n], Mod - 2);

	for(int i = n - 1; i; --i) invjc[i] = 1ll * invjc[i + 1] * (i + 1) % Mod;

	for(int i = 0; i <= n; ++i) a[i] = 1ll * invjc[i] * (i & 1 ? Mod - 1 : 1) % Mod;

	for(int i = 2; i <= n; ++i)

		b[i] = 1ll * (qpow(i, n + 1) + Mod - 1) % Mod * qpow(i - 1, Mod - 2) % Mod * invjc[i] % Mod;

	for(m = n << 1, n = 1; n <= m; n <<= 1, ++P);

	for(int i = 0; i < n; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));

	NTT(a, 1), NTT(b, 1);

	for(int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % Mod;

	NTT(a, -1); int invn = qpow(n, Mod - 2);

	for(int i = 0; i <= n; ++i)

		ret = (ret + 1ll * pow2[i] * jc[i] % Mod * a[i] % Mod * invn % Mod) % Mod;

	printf("%d\n", ret);

	return 0;

}

巴特西

【Bzoj4555】【Luogu P4091】求和（NTT）

题面

题解

最新文章

热门文章