题目大意：给你$n(nleqslant10^5)$，求：
$$
sumlimits_{i=0}^nsumlimits_{j=0}^iegin{Bmatrix}i\jend{Bmatrix} imes2^j imes j!
$$
$egin{Bmatrix}n\mend{Bmatrix}$表示第二类斯特林数，递推公式为$egin{Bmatrix}n\mend{Bmatrix}=megin{Bmatrix}n-1\mend{Bmatrix}+egin{Bmatrix}n-1\m-1end{Bmatrix}(1leqslant mleqslant n-1)$，边界为$egin{Bmatrix}n\nend{Bmatrix}=1(0leqslant n),egin{Bmatrix}n\0end{Bmatrix}=0(1leqslant n)$
题解：第二类斯特林数表示把$n$个不相同的球放在$m$个相同的盒子里，没有空的盒子。可以枚举至少有几个空的盒子来容斥。
$$
egin{Bmatrix}n\mend{Bmatrix}=dfrac1{m!}sumlimits_{i=0}^minom mi(-1)^i(m-i)^n
$$
直接带到原式子中
$$
egin{align*}
&sumlimits_{i=0}^nsumlimits_{j=0}^iegin{Bmatrix}i\jend{Bmatrix} imes2^j imes j!\
=&sumlimits_{i=0}^nsumlimits_{j=0}^idfrac1{j!}sumlimits_{k=0}^jinom jk(-1)^k(j-k)^i imes2^j imes j!\
=&sumlimits_{i=0}^nsumlimits_{j=0}^isumlimits_{k=0}^jdfrac{j!}{k!(j-k)!}(-1)^k(j-k)^i imes2^j\
=&sumlimits_{i=0}^nsumlimits_{j=0}^i2^jj!sumlimits_{k=0}^jdfrac{1}{k!(j-k)!}(-1)^k(j-k)^i\
end{align*}
$$
发现若$egin{Bmatrix}n\mend{Bmatrix}$中$m>n$，值为$0$。可以把$j$的上界变为$n$
$$
egin{align*}
=&sumlimits_{i=0}^nsumlimits_{j=0}^n2^jj!sumlimits_{k=0}^jdfrac{1}{k!(j-k)!}(-1)^k(j-k)^i\
=&sumlimits_{j=0}^n2^jj!sumlimits_{k=0}^jdfrac{(-1)^k}{k!}dfrac{sumlimits_{i=0}^n(j-k)^i}{(j-k)!}\
=&sumlimits_{j=0}^n2^jj!sumlimits_{k=0}^jdfrac{(-1)^k}{k!}dfrac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!}
end{align*}
$$
令$f_i=dfrac{(-1)^i}{i!},g_i=dfrac{i^{n+1}-1}{(i-1)i!}$
$$
egin{align*}
=&sumlimits_{j=0}^n2^jj!;[j](f*g)
end{align*}
$$
$FFT$一下就好了
卡点：无
C++ Code：
#include <algorithm>
#include <cstdio>
#define maxn 262144
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
namespace Math {
inline int pw(int base, int p) {
static int res;
for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
return res;
}
inline int inv(int x) { return pw(x, mod - 2); }
}
namespace Poly {
#define N maxn
int lim, s, rev[N];
int Wn[N | 1];
inline void init(const int n) {
lim = 1, s = -1; while (lim < n) lim <<= 1, ++s;
for (int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
const int t = Math::pw(3, (mod - 1) / lim);
*Wn = 1; for (register int *i = Wn; i != Wn + lim; ++i) *(i + 1) = static_cast<long long> (*i) * t % mod;
}
inline void FFT(int *A, const int op = 1) {
for (register int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
for (register int mid = 1; mid < lim; mid <<= 1) {
const int t = lim / mid >> 1;
for (register int i = 0; i < lim; i += mid << 1)
for (register int j = 0; j < mid; ++j) {
const int X = A[i + j], Y = static_cast<long long> (A[i + j + mid]) * Wn[t * j] % mod;
reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y);
}
}
if (!op) {
const int ilim = Math::inv(lim);
for (register int *i = A; i != A + lim; ++i) *i = static_cast<long long> (*i) * ilim % mod;
std::reverse(A + 1, A + lim);
}
}
void Mul(int *A, int *B, int n) {
init(n << 1);
FFT(A), FFT(B);
for (int i = 0; i < lim; ++i) A[i] = static_cast<long long> (A[i]) * B[i] % mod;
FFT(A, 0);
}
#undef N
}
int n;
int f[maxn], g[maxn];
int fac[maxn], inv[maxn], pinv[maxn];
int main() {
scanf("%d", &n);
fac[0] = fac[1] = inv[0] = inv[1] = pinv[0] = pinv[1] = 1;
for (int i = 2; i <= n; ++i) {
fac[i] = static_cast<long long> (fac[i - 1]) * i % mod;
inv[i] = static_cast<long long> (mod - mod / i) * inv[mod % i] % mod;
pinv[i] = static_cast<long long> (pinv[i - 1]) * inv[i] % mod;
}
g[0] = 1, g[1] = n + 1;
for (int i = 2; i <= n; ++i) g[i] = static_cast<long long> (Math::pw(i, n + 1) - 1) * inv[i - 1] % mod * pinv[i] % mod;
for (int i = 0; i <= n; ++i) f[i] = static_cast<long long> ((i & 1) ? mod - 1 : 1) * pinv[i] % mod;
Poly::Mul(f, g, n + 1);
for (int i = 0; i <= n; ++i) f[i] = static_cast<long long> (f[i]) * fac[i] % mod * Math::pw(2, i) % mod;
int ans = 0;
for (int i = 0; i <= n; ++i) reduce(ans += f[i] - mod);
printf("%d
", ans);
return 0;
}