题意：

一个长为的排列，有两个人轮流从中取数，每一轮中所取的数需要满足如下规则：

  1. 取的数大于之前所有人取的数
  2. 取的数的下标大于取数人之前取的数的下标
  3. 如果有多种取数方案，则随机进行取数
  4. 第一个人第一次取数随机
  5. 如果有人没法再取数，游戏结束

求最后期望能取数多少次。

Solution:

期望DP，比赛时最后想到了做法但是没写完，晚上调了调就过了。

首先想到一个状态：表示当前轮选择了第个位置，前一轮选择了第个位置时，游戏期望还能进行的轮数（包括当前轮）。

现在我们考虑这个状态能从哪些地方转移过来，即按照正常的游戏顺序，下一轮该如何选择，按照规则我们知道，下一轮能选择的位置必须满足如下条件：

1.

2.

设所有满足条件的k的数量为，则转移方程为

初始状态为，其中为任意数，为最大数的下标

最后的答案为

因为只需要保证，所以和的大小关系不确定，因此按照下标从大到小计算是不行的，可能会统计到还没有计算的状态。因此，为了保证能顺利转移，我们按照数组从大到小排序，按照排序后原本下标的顺序进行计算，这样就可以保证统计到的都是已经计算过的状态了，转移的时候每次需要统计大于的下标中，值大于的所有状态的和，单次转移的复杂度为，倒序枚举，对同一个，用一个记录之前状态的和可以把单次转移复杂度将为，这样的话总复杂度就为。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[5010],inv[5010];
struct poss{
    int id,v;
}a[5010];
int f[5010][5010],pos[5010];
bool cmp(poss a,poss b)
{
    return a.v>b.v;
}
const int mod=998244353;
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        a[i].id=i,a[i].v=p[i];
    }
    sort(a+1,a+1+n,cmp);
    for (int i=0;i<=n;i++)
        f[a[1].id][i]=1,f[i][n]=1,pos[a[i].v]=i;
    for (int i=1;i<=n;i++)
        inv[i]=fast_pow(i,mod-2);
    for (int i=2;i<=n;i++)
    {
        int sum=0,num=0;
        for (int j=n-1;j>=0;j--)
        {
            if (p[j+1]>a[i].v)
            {
                sum+=f[j+1][a[i].id],num++;
                if (sum>=mod) sum-=mod;
            }
            f[a[i].id][j]=(1ll*sum*inv[num]+1)%mod;
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)
        ans=(ans+f[i][0])%mod;
    printf("%d\n",1ll*(ans)*inv[n]%mod);
}