CF1349F1 Slime and Sequences (Easy Version) 题解

题意：https://www.luogu.com.cn/problem/CF1349F1
首先这个序列中有相同元素，我们考虑逆排列。
把每个数出现的位置依次排列，相同的数字位置递减排列。
容易发现，在a(i+1)>a(i)的位置插入一条分割线即可。
设f(x,y)表示长度x的排列，有y个位置满足p(i+1)>p(i)的方案数。
f(x,y)即为欧拉数。
那么我们考虑f(x,y)新加入一个最大的数。若插入y个相邻位置之间或者放到最开始则y不变，其余情况y增加1。
这样f可以\(O(n^2)\)递推。
统计答案时，我们枚举k的出现位置a，把答案加上f(a,k-1)C(n,a)(n-a)!即可。
代码：

#include 
#define md 998244353
int f[5010][5010],jc[5010],ny[5010],jn[5010];
void yucl(int n)
{
    f[1][0]=jc[0]=jn[0]=ny[1]=1;
    for(int i=2;i<=n;i++)
        ny[i]=1ll*(md-md/i)*ny[md%i]%md;
    for(int i=1;i<=n;i++)
        jc[i]=1ll*i*jc[i-1]%md,jn[i]=1ll*ny[i]*jn[i-1]%md;
    for(int x=1;x