思路

方法一

状态方程：

状态方程中的 ${i，j}$ 表示的是数组的下标，即位置。

${f[i][j][0]}$ ，表示 ${Alice}$ 上一步选了 ${i}$ ， ${Bob}$ 上一步选了 ${j}$ ，这一轮是 ${Alice}$ 选择，从上一轮开始游戏进行的回合数的期望（即从 ${Bob}$ 选 ${j}$ 开始计数）；

${f[i][j][1]}$ ，表示 ${Alice}$ 上一步选了 ${i}$ ， ${Bob}$ 上一步选了 ${j}$ ，这一轮是 ${Bob}$ 选择，从上一轮开始游戏进行的回合数的期望（即从 ${Alice}$ 选 ${i}$ 开始计数）

状态转移方程：

${f[i][j][0]=(\sum_{k>i\&\& a[k]>a[j]}{f[k][j][1]*p})+1}$

${f[i][j][1]=(\sum_{k>j\&\& a[k]>a[i]}{f[i][k][0]*p})+1}$

${p}$ 表示事件发生的概率

运行超时的代码：code

考虑一下优化：

首先记忆化搜索保证只会对 ${n*n*2}$ 种情况进行搜索，可以考虑把每种情况里面的一层 ${for}$ 循环给消掉。

1:
if(s) {
    int cnt=c[p2+1][a[p1]];
    for(int i=p2+1;i<=n;++i) if(a[i]>a[p1])
        ans=(ans+(dfs(p1,i,0)+1)*inv[cnt]%mod)%mod;
}

2:
if(s){
    int cnt=c[p2+1][a[p1]];
    if(a[p1]>a[p2]){
         ans=qu(ans+qu(qu(dfs(p1,p2+1,0)*inv[cnt])+1ll));
    }
    ans=qu(ans+dfs(p1+1,p2,1));
}

代码 ${1}$ 中当 ${(a[i]>a[p1]\&\& i> p2)}$ 时才能产生新的情况。如果记 ${f[p1][p2][0]=\sum_{i=p2}^{n}{f[p1][i][0]}}$ ，调用 ${dfs(p1,p2,0)}$ 求 ${f[p1][p2][0]}$ 时，当 ${(a[p1]>a[p2])}$ 时，表明这个状态合法，这时才会进行新的状态调用 ${dfs(p1+1,p2,1)}$ ，接着会套娃调用 ${dfs(p1+2,p2,1)...dfs(n,p2,1)}$ 。就可以成功消掉一层循环了。

列如，下面是调用 ${dfs(p 1,p2,0)}$ 后的部分过程

dfs(p1+1,p2,1);//a[p2]>a[p1]
dfs(p1,p2+1,0);

dfs(p1+1+1,p2,1)//a[p2]>a[p1+1+1]
dfs(p1+1,p2+1,0);

...

假如 ${a[k]>a[i],k\in \{b_1,b_2,,b_x\}}$ ，那么答案其实就是 ${E(i,k,0)}/x+1$ , ${E(i,k,0)}$ 表示 ${Alice}$ 选 ${a[i]，Bob}$ 选 ${a[k]}$ ，选择轮到 $Alice$ 来选，进行回合数的期望（包括 ${Bob}$ 选 ${a[k]}$ 的这一回合），直接写成 ${dfs(i,1,0)/x+1}$ 就行了。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5002,mod=998244353;
int n,a[maxn],c[maxn][maxn];
int inv[maxn];
int dp[maxn][maxn][2];
ll dfs(int p1,int p2,int s){
    if(p1>n||p2>n) return 0;
    if(~dp[p1][p2][s]) return dp[p1][p2][s];
    ll ans=0;
    if(s==0){
        int cnt=c[p1+1][a[p2]];
        if(a[p2]>a[p1])
            ans=(ans+((dfs(p1+1,p2,1)*inv[cnt])%mod+1ll)%mod)%mod;
        ans=(ans+dfs(p1,p2+1,0))%mod;
    }else{
        int cnt=c[p2+1][a[p1]];
        if(a[p1]>a[p2])
            ans=(ans+((dfs(p1,p2+1,0)*inv[cnt])%mod+1ll)%mod)%mod;
        ans=(ans+dfs(p1+1,p2,1))%mod;
    }
    return dp[p1][p2][s]=ans;
}
int main(){
    scanf("%d",&n);
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    inv[1] = 1;for(int i = 2;i <= n;i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i=n;i>=1;--i){
        for(int j=1;j<=n;++j){
            c[i][j]=c[i+1][j];
            if(j<a[i]) c[i][j]++;
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        int cnt=c[1][a[i]];
        res=(res+(((dfs(i,1,0)*inv[cnt])+1ll)%mod*inv[n])%mod)%mod;
        //优化前的代码：res=(res+(dfs(i,0,1)+1)*inv[n]%mod)%mod;
    }
    printf("%lld\n",res);
}

方法二

思路：

设 ${f[i][j]}$ 表示一个人上一次选的是 ${i}$ 另一个人上一次选的是 ${j}$ ,接下来游戏结束的期望值。这里 ${i,j}$ 表示的是值，不是下标。

那么就有： ${f[i][j]=\frac{\sum_{a_k>j,且k大于i的下标}f[j][a_k]}{cnt},cnt=k的数量}$

从大到小枚举值 $j$ ,接着从大到小枚举位置 ${k}$ 。如果 ${a[k]>j}$ ，记录 $f[j][a[k]]$ 的前缀和以及个数，否则更新 $f[a[k]][j]$ 的值。即： ${f[a[k]][j]=\frac{\sum_{x=k}^{n}[a_x>j]f[j][a_x]}{cnt},cnt=x的数量}$

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,a[5005],inv[5005],f[5005][5005];
int main() {
    scanf("%d",&n);
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    for(int j=n; ~j; j--) {
        int sum=0,cnt=0;
        for(int i=n; ~i; i--) {
            if(a[i]==j) continue;
            if(a[i]>j) cnt++,sum=(sum+f[j][a[i]])%mod;
            else f[a[i]][j]=(1ll*sum*inv[cnt]+1)%mod;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = (ans + f[0][i]) % mod;
    printf("%d", 1ll * ans * inv[n] % mod);
    return 0;
}

Increasing Subsequence

思路

方法一

方法二