题解 | #Alice and Bob#

I题

具体看代码里的注释

#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
typedef long long LL;
const double eps=1e-7;

LL a[N],inv[N];
LL n;
LL qsm(LL a,LL n){
    LL res=1;
    while(n){
        if(n&1)res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        n>>=1;
    }
    return res;
}
LL  f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)inv[i]=qsm(i,mod-2);
    //记住，这里是往后递推，类似拓扑图
    //逆着写期望DP，这里发现，每一次与上一次的值有关，下标逆着推能够很好的处理游戏轮数
    for(int j=n;j>=0;j--){//这次选择J，从大到小
        LL cnt=0,sum=0;//期望和,也就是这次选择的数大于J，所有期望和，cnt,均等概率
        for(int i=n;i>=0;i--){// 下一次选择的a[i]
            if(a[i]>j)//说明这里已经计算过了
            {
                cnt++;//往前做的时候可以累加大于 J 的下标个数
                sum+=f[j][a[i]];//所有期望和
                sum%=mod;
            }
            else if(a[i]<j){//下一次不可能选择a[i],所以这一次选择a[i],下一次选择J能够更新，
                //这里上一次是J，这一次是a[i]的方案根本不存在
                f[a[i]][j]=1;//这里期望必有 1 ，就是转移到这个状态有一轮，不管这人是谁，选择的是a[i]，游戏轮数是1，能否被其他状态转移过来呢？
                if(!cnt)continue;
                f[a[i]][j]+=sum*inv[cnt]%mod;//加上后面他可以转移的，遵循均等的原则
                f[a[i]][j]%=mod;
            }
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++)
        res=(res+f[0][i])%mod;
    //最后第一个也是均等选择的
    res=res*inv[n]%mod;
    cout<<res<<endl;
    return 0;

}