发现样例中所有数的和为 \(n!n\)，于是猜想好的序列总数为 \(n!\)。
考虑将每一个排列 \(p\) 唯一对应一个好的序列 \(a\)。可以这么构造：在 \(p\) 中顺着填，先倒着列出 \(1\) 在 \(a\) 中所有出现位置，再到 \(2,3,...,n\)。
于是发现对于一个排列 \(p\)，\(i\) 出现的次数就是第 \(i\) 个连续极长的大于段的长度。所以当且仅当 \([1,j)\) 中有 \(i-1\) 个位置 \(k\) 满足 \(p_k < p_{k+1}\)，\(j\) 就对 \(ans_i\) 造成了 \(1\) 的贡献。
设 \(f_{i,j}\) 有多少种 \(1 \sim i\) 的排列满足存在 \(j\) 个位置 \(p\) 满足 \(p_k < p_{k+1}\)，可得：
\[ans_i = \sum\limits_{j=1}^n f_{j,i-1} \times \dbinom{n}{j} \times (n-j)! \]意思是从 \(n\) 个数选 \(j\) 个，剩下 \(n-j\) 个数随便放。
\(f_{i,j}\) 可以 dp 求出。考虑将 \(i\) 插入 \(1 \sim i-1\) 的排列中，需要分类讨论：
- 若插到开头，则从 \(f_{i-1,j}\) 转移；
- 若插到结尾，则从 \(f_{i-1,j-1}\) 转移；
- 若插到满足 \(p_k < p_{k+1}\) 的 \(k,k+1\) 之间，则从 \(j \times f_{i-1,j}\) 转移；
- 若插到满足 \(p_k > p_{k+1}\) 的 \(k,k+1\) 之间，则从 \((i-j-1) \times f_{i-1,j-1}\) 转移。
综上，有 \(f_{i,j} = (j+1)f_{i-1,j} + (i-j)f_{i-1,j-1}\)。
总时间复杂度 \(O(n^2)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5010;
const ll mod = 998244353;
ll n, fac[maxn], ifac[maxn];
ll f[maxn][maxn];
ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld", &n);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
f[1][0] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
f[i][j] = f[i - 1][j] * (j + 1) % mod;
if (j) {
f[i][j] = (f[i][j] + f[i - 1][j - 1] * (i - j) % mod) % mod;
}
}
}
for (int i = 1; i <= n; ++i) {
ll ans = 0;
for (int j = 1; j <= n; ++j) {
ans = (ans + f[j][i - 1] * C(n, j) % mod * fac[n - j] % mod) % mod;
}
printf("%lld ", ans);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}