$$f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ i S(i, j) \times 2 ^ j \times j!$$

\begin{aligned} f(n) &= \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n S(i, j) \times 2 ^ j \times j! \\ &= \sum _ {j = 0} ^ n 2 ^ j! \times \sum _ {i = 0} ^ n S(i, j) \end{aligned}

$$S(n, k) = \frac 1 {k!} \times \sum _ {i = 0} ^ k (-1) ^ i \times C _ k ^ i \times (k – i) ^ n$$

\begin{aligned} f(n) &= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n S(i, j) \\ &= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n [\frac 1 {j!} \times \sum _ {k = 0} ^ j (-1) ^ k \times C _ j ^ k \times (j – k) ^ i] \\ &= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n \sum _ {k = 0} ^ j [\frac {(-1) ^ k} {k!} \times \frac {(j – k) ^ i} {(j – k)!}] \\ &= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {k = 0} ^ j [\frac {(-1) ^ k} {k!} \times \frac {\sum _ {i = 0} ^ n (j – k) ^ i} {(j – k)!}] \end{aligned}

$$f(i) = \frac {(-1) ^ i} {i!}$$
$$g(i) = \frac {\sum _ {j = 0} ^ n i ^ j} {i!}$$

$g$可以用等比数列求和公式算

$$f(n) = \sum _ {i = 0} ^ n 2 ^ i \times i! \times (f \times g)(i)$$

#include <bits/stdc++.h>

#define NS (262150)
#define MOD (998244353)
#define G (3)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = mul(res, a);
a = mul(a, a), b >>= 1;
}
return res;
}

int n, fac[NS], fiv[NS];

int rev[NS];

struct poly
{
int d[NS], N, bs;
int& operator [] (const int a) {return d[a];}
void resize(int l)
{
N = 1, bs = 0;
while (N < l) N <<= 1, bs++;
}
void ntt(int t)
{
for (int i = 0; i < N; i += 1)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
if (i < rev[i]) swap(d[i], d[rev[i]]);
}
for (int l = 1; l < N; l <<= 1)
{
int dt = qpow(G, (MOD - 1) / (l << 1));
if (t == -1) dt = inv(dt);
for (int i = 0; i < N; i += (l << 1))
{
int g = 1, t1, t2;
for (int j = i; j < i + l; j += 1, g = mul(g, dt))
{
t1 = d[j], t2 = mul(d[j + l], g);
d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
}
}
}
if (t == -1)
{
int iv = inv(N);
for (int i = 0; i < N; i += 1) d[i] = mul(d[i], iv);
}
}
void operator *= (poly &oth)
{
for (int i = 0; i < N; i += 1) d[i] = mul(d[i], oth[i]);
}
} A, B;

int main(int argc, char const* argv[])
{
IN(n), A.resize(n << 1 | 1), B.resize(n << 1 | 1), fac[0] = 1;
for (int i = 1; i <= n; i += 1) fac[i] = mul(fac[i - 1], i);
fiv[n] = inv(fac[n]);
for (int i = n - 1; i >= 0; i -= 1) fiv[i] = mul(fiv[i + 1], (i + 1));
for (int i = 0; i <= n; i += 1)
{
if (i & 1) A[i] = mul(mns(0, 1), fiv[i]);
else A[i] = fiv[i];
if (i == 1) B[i] = pls(n, 1);
else B[i] = mul(mul(mns(qpow(i, n + 1), 1), inv(mns(i, 1))), fiv[i]);
}
A.ntt(1), B.ntt(1), A *= B, A.ntt(-1);
int ans = 0;
for (int i = 0, j = 1; i <= n; i += 1, j = pls(j, j))
ans = pls(ans, mul(mul(j, fac[i]), A[i]));
printf("%d\n", ans);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.