题目描述
定义一个正整数序列\(\texttt{p}\)，称其是合法的当且仅当对于所有在\(\texttt{p}\)中出现过且\(> 1\)的正整数\(k\)，存在\(i<j\)，满足\(p_i=k-1,p_j=k\)。
定义\(f(k)\)为\(k\)在所有长度为\(n\)的好序列中的出现次数之和。
\(\forall k\in[1,n]\)求\(f(k)\)。
\(n\leq 5000\)
解题思路
非常妙的映射！
可证明每个合法序列和一个排列一一对应：
- 1.考虑怎么把排列对应成一个合法序列：
考虑把排列划分成若干极长的连续下降段，若第\(i\)段里有数\(x\)，就让\(p_x=i\)。
这样构造的\(p\)一定是合法的，否则就说明存在一个\(k\)，使得所有\(k\)的出现位置都在\(k-1\)的出现位置前面，那么这两个连续段应该会变成一个，就矛盾了。
- 2.一个合法序列对应一个排列
这是显然的，把上述过程逆过来就好了。
因此这是一个双射。
那么对于一个位置\(i\)，它对\(f(k)\)的贡献就是它被划分在第\(k\)段的排列数。
对于位置\(i\)，若\(p_i<p_{i+1}\)，我们称之为一个上升。
则\(i\)被划分在第\(k\)段的排列数等价与前\(i\)个位置恰好有\(k-1\)个上升。
设长度为\(n\)且有\(m\)个上升的排列个数为\(dp_{n,m}\)，则
\[f(k)=\sum_{i=1}^ndp_{i,k-1}C_n^i(n-i)! \]\(dp_{n,m}\)的递推是好求的，考虑加入最小的数：
-
加入后上升个数不变，有\(m+1\)种选择，因为可以填到末尾
-
加入后上升个数加一，有\(n-m\)种选择，因为可以填到开头
总复杂度\(O(n^2)\).
#include<bits/stdc++.h>
using namespace std;
const int N = 5050;
int dp[N][N];
int n;
const int mod = 998244353;
inline int myplus(int a,int b){return (a+b>=mod?a+b-mod:a+b);}
int ans[N],C[N][N],fac[N];
int main()
{
cin>>n;
dp[1][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i-1;j++)
{
dp[i+1][j]=myplus(dp[i+1][j],1ll*dp[i][j]*(j+1)%mod);
dp[i+1][j+1]=myplus(dp[i+1][j+1],1ll*dp[i][j]*(i-j)%mod);
}
C[0][0]=1;fac[0]=1;
for(int i=1;i<=n;i++)
{
fac[i]=1ll*fac[i-1]*i%mod;
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=myplus(C[i-1][j-1],C[i-1][j]);
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
ans[k]=myplus(ans[k],1ll*dp[i][k-1]*C[n][i]%mod*fac[n-i]%mod);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}