Increasing Subsequence

题目描述

给定一个长度为 n(n<=5000) 的排列,两个人轮流从这个序列中选择一个数,要求当前回合此人选择的数大于任意一个已经被选择的数,并且该数在数组中的位置 i 与此人上一次选择的数在数组中的位置 j 要满足 i>j,如果有多个数合法则等概率的从这些数中选一个。当没有合法数时结束,问最终被选择的数的期望个数。

Solution

考虑状态 dp[x][y] 表示从当前此人上一次选了 x ,另一个人选了 y ,又该这个人选择 开始到游戏结束轮数的期望值。

则有

dp[x][y] = \frac{\sum _1^{cnt}dp[y][z]}{cnt}+1

其中 z>y ,且 pos(z)>pos(x)pos(x) 表示大小为 x 的数在原序列中的下标位置。

处理时,我们先枚举第二维的 y ,通过统计 z>y 的情况,并且处理一个与原序列下标有关的前缀和。然后再枚举 x 向前转移就好。

#include<bits/stdc++.h>
#define ll long long
const int N = 5010;
const ll mod = 998244353;
int n,a[N],pos[N],sum[N],c[N],dp[N][N],inv[N];
ll qpow(ll a,ll b){
    if(b==0) return 1;
    ll p = qpow(a,b/2);
    p = p * p %mod;
    if(b&1) p = p * a %mod;
    return p;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),pos[a[i]]=i,inv[i]=qpow(i,mod-2);
    for(int j=n;j;--j){
        memset(c,0,sizeof c);
        memset(sum,0,sizeof sum);
        for(int i=j+1;i<=n;++i){
            c[pos[i]]++;
            sum[pos[i]] = dp[j][i];
        }
        for(int i=n-1;i+1;--i){
            c[i]+=c[i+1];
            sum[i]+=sum[i+1];
            sum[i]%=mod;
        }
        for(int i=j-1;i>=0;--i){
            ll t = c[pos[i]];
            ll s = sum[pos[i]];
            if(t)
                dp[i][j] = (s*inv[t]+1)%mod;
        }
    }
    ll ans = 0 ;
    for(int i=1;i<=n;++i)
        ans = (ans + dp[0][i]) %mod;
    ans = (ans *inv[n] +1 )%mod;
    printf("%lld",ans);
    return 0;
} 
分类: 期望计数

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注