<span role="heading" aria-level="2">luogu P4091 [HEOI2016/TJOI2016]求和 FFT</span>

又是一道神仙题orz

我们先化一化式子。

$\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)$

看着$\displaystyle \sum_{j=0}^i$很不爽，因为当$j>i$时，$S(i,j)=0$,所以

$\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times (j!)$

看着$S(i,j)$很不爽，我们先把它单独拎出来。

$\displaystyle Ans[n]=\sum_{j=0}ⁿ²j\times (j!)\sum_{i=0}^nS(i,j) $

注意这里枚举$i,j$的顺序发生了改变，但式子依然等价。

这里先放个结论:

$\displaystyle S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i$

这个可以用容斥原理来解释，第二类斯特林数是将i个不同的球，j个相同的盒子，不能空的方案数，现将盒子看成不一样的，并且能空，枚举空盒的个数$C_{j}^{k}$, 其余的随便放$(j-k)^i$, 乘上容斥系数$(-1)^k$,在乘上$\displaystyle \frac{1}{j!}$将盒子变成一样的。

带进$\displaystyle S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i$发现:

$\displaystyle Ans[n]=\sum_{j=0}ⁿ²j\times (j!)\sum_{i=0}^n \frac{1}{j!}\sum_{k=0}^j(-1)k C_{j}^{k} (j-k)^i $

$\displaystyle Ans[n]=\sum_{j=0}ⁿ²j \sum_{i=0}^n \sum_{k=0}^j(-1)k C_{j}^{k} (j-k)^i $

将$\displaystyle C_j^k=\frac{j!}{k!(j-k)!}$ 带进去。

$\displaystyle Ans[n]=\sum_{j=0}ⁿ²j \sum_{i=0}^n \sum_{k=0}^j(-1)k \frac{j!}{k!(j-k)!} (j-k)^i $

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{i=0}^n \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!} $

看着$\displaystyle \frac{(j-k)^i}{(j-k)!}$非常不清真，又因为只有它带着$i$,所以我们再次改变枚举顺序。

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{\sum_{i=0}^n(j-k)i}{(j-k)!} $

我们设$\displaystyle f[k]=\frac{(-1)^k}{k!}$ $\displaystyle g[k]=\frac{\sum_{i=0}^n k^i}{k!}$式子就变成了

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{k=0}^j f[k]g[j-k] $

$ \displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! (f*g)(j) $

$(f*g)(j)$的含义就是$f$卷上$g$后$x^j$的系数。

后面的$\displaystyle g[k]=\frac{\sum_{i=0}^n k^i}{k!}$貌似可以等比数列求和，根据等比数列求和的知识我们知道$\displaystyle \sum_{i=0}^n k^i=\frac{k^{n+1}-1}{k-1}$

所以$\displaystyle g[k]=\frac{k^{n+1}-1}{(k-1)k!}$

注意

$g[0]=1$（$0^0$并没有意义，但是$S(0,0)=1$,所以$g[0]=1$）。

$g[1]=n+1$,（k=1时并不能等比数列求和，但显然$g[1]=n+1$）

NTT一波带走就行了。

#include<iostream>
#include<cstdio>
#define DB double
#define LL long long
using namespace std;
int n;
const int N = 400010, mod = 998244353, G = 3, Ginv = (mod + 1) / 3;
int r[N];
LL ans, two = 1;
LL g[N], f[N], jc[N], inv[N];
LL ksm(LL a, LL b, LL mod) 
{
	LL res = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1)res = res * a % mod;
	return res;
}
void NTT(LL *A, int lim, int opt) 
{
	for (int i = 0; i < lim; ++i)
		if (i < r[i])swap(A[i], A[r[i]]);
	int len;
	LL wn, w, x, y;
	for (int mid = 1; mid < lim; mid <<= 1) 
	{
		len = mid << 1;
		wn = ksm(opt == 1 ? G : Ginv, (mod - 1) / len, mod);
		for (int j = 0; j < lim; j += len) 
		{
			w = 1;
			for (int k = j; k < j + mid; ++k, w = w * wn % mod) 
			{
				x = A[k]; y = A[k + mid] * w % mod;
				A[k] = (x + y) % mod;
				A[k + mid] = (x - y + mod) % mod;
			}
		}
	}
	if (opt == 1)return;
	int ni = ksm(lim, mod - 2, mod);
	for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}
void MUL(LL *A, int n, LL *B, int m) 
{
	int lim = 1;
	while (lim < (n + m))lim <<= 1;
	for (int i = 0; i < lim; ++i)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
	NTT(A, lim, 1); NTT(B, lim, 1);
	for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
	NTT(A, lim, -1);
}
void YYCH() 
{
	inv[0] = inv[1] = jc[0] = jc[1] = 1;
	for (int i = 2; i <= n; ++i)jc[i] = jc[i - 1] * i % mod;
	inv[n] = ksm(jc[n], mod - 2, mod);
	for (int i = n - 1; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;
	for (int i = 0; i <= n; ++i)f[i] = (i & 1) ? mod - inv[i] : inv[i];
	g[0] = 1; g[1] = n + 1;
	for (int i = 2; i <= n; ++i)
		g[i] = (ksm(i, n + 1, mod) - 1) * ksm(i - 1, mod - 2, mod) % mod * inv[i] % mod;
}
int main() 
{
	cin >> n;
	YYCH();
	MUL(f, n, g, n);
	for (int i = 0; i <= n; ++i, two = two * 2 % mod)
		(ans += two * jc[i] % mod * f[i] % mod) %= mod;
	cout << ans;
	return 0;
}