题意：
现在有一个人分别从\(1,n\)两点出发，包中有一个物品价值一开始为\(0\)，每遇到一个价值比包中物品高的就交换两个物品。
现在已知这个人从左边出发交换了\(a\)次，从右边出发交换了\(b\)次。
现在问有多少个排列满足这一条件。
思路：
- 倒过来考虑的话，显然全局最大值为最后一次交换。
- 然后左边我们会放置\(a-1\)个递增的物品，右边放\(b-1\)个递减的物品，其余的物品我们在中间部分任意放置即可，但要保证价值在一定范围。
- 将问题进一步抽象，我们即要将\(n-1\)个数划分为\(a+b-2\)个排列，因为每个排列都有一个最大值，所以一定存在一种合法放案使得每个排列中只会交换一次。
- 因为最后还有两个部分，所以还要乘以一个组合数，那么答案就是\(\displaystyle \begin{bmatrix}
n - 1 \\ a - b + 2
\end{bmatrix}\cdot {a-b+2\choose a-1}\) 。 - 那么问题就是如何快速处理一行的第一类斯特林数了。主要是通过生成函数来求解，详细内容可以见：传送门
正难则反，正过来考虑较为复杂的情况，倒过来就显得清晰很多。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2019/12/15 10:30:30
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5, MOD = 998244353;
int n, a, b;
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
int inv[N], fac[N];
void init() {
fac[0] = 1;
for(int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[N - 1] = qpow(fac[N - 1], MOD - 2);
for(int i = N - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int r[N], W[N];
void NTT(int *P, int opt, int N) {
int l = 0; for(int i = 1; i < N; i <<= 1) ++l;
for(int i = 0; i < N; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for(int i = 0; i < N; i++) if(i < r[i]) swap(P[i], P[r[i]]);
for(int i = 1; i < N; i <<= 1) {
int w = qpow(3, (MOD - 1) / (i << 1)); W[0] = 1;
for(int k = 1; k < i; k++) W[k] = 1ll * W[k - 1] * w % MOD;
for(int p = i << 1, j = 0; j < N; j += p) {
for(int k = 0; k < i; k++) {
int X = P[j + k], Y = 1ll * W[k] * P[i + j + k] % MOD;
P[j + k] = (X + Y) % MOD;
P[i + j + k] = (X + MOD - Y) % MOD;
}
}
}
if(opt == -1) {
reverse(P + 1, P + N);
int inv = qpow(N, MOD - 2);
for(int i = 0; i < N; i++) P[i] = 1ll * P[i] * inv % MOD;
}
}
int S[N];
int A[N], B[N], pw[N];
void solve(int len) {
if(len == 0) {S[0] = 1; return;}
if(len == 1) {S[1] = 1; return;}
if(len & 1) {
solve(len - 1);
for(int i = len; i; i--) S[i] = (S[i - 1] + 1ll * S[i] * (len - 1)) % MOD;
} else {
solve(len >> 1); int l = len >> 1, N;
for(N = 1; N <= len; N <<= 1);
pw[0] = 1;
for(int i = 1; i <= l; i++) pw[i] = 1ll * pw[i - 1] * l % MOD;
for(int i = 0; i <= l; i++) A[i] = 1ll * S[i] * fac[i] % MOD;
for(int i = 0; i <= l; i++) B[i] = 1ll * pw[i] * inv[i] % MOD;
reverse(B, B + l + 1);
NTT(A, 1, N); NTT(B, 1, N);
for(int i = 0; i < N; i++) A[i] = 1ll * A[i] * B[i] % MOD;
NTT(A, -1, N);
for(int i = 0; i <= l; i++) A[i] = 1ll * A[i + l] * inv[i] % MOD;
for(int i = l + 1; i < N; i++) A[i] = B[i] = 0;
for(int i = 0; i <= l; i++) B[i] = S[i];
NTT(A, 1, N); NTT(B, 1, N);
for(int i = 0; i < N; i++) A[i] = 1ll * A[i] * B[i] % MOD;
NTT(A, -1, N);
for(int i = 0; i <= len; i++) S[i] = A[i];
for(int i = 0; i < N; i++) A[i] = B[i] = 0;
}
}
void run(){
init();
solve(5);
for(int i = 0; i <= 5; i++) cout << S[i] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}