2021牛客多校第一场 I题(DP)

题意

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

分析

考虑 (dp) ，设 (dp[x][y]) 为当前轮到此人选数并且他上一次选了数 (x)，另一个人选了数 (y) 开始到游戏结束时选择的数的期望个数。则 (dp[x][y] = inv[tot] * sum_{i=1}^{tot} dp[y][a_i] + 1)，(tot) 为可选择的数字的个数，(a_{i}) 为可选的数字。首先枚举 (y) ，然后用前缀和处理一下即可 (O(1)) 完成转移，再枚举 (x)，总复杂度 (O(n^2)。)。

代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
constexpr int N = 5005;
const int MOD = 998244353;

int T, n;
int p[N], c[N], sum[N], pos[N], inv[N];
int dp[N][N];

int qpow(int x, int k) {
    int ret = 1;
    while(k) {
        if(k & 1)  ret = (ll) ret * x % MOD;
        x = (ll) x * x % MOD;
        k >>= 1;
    }
    return ret;
}

int main() {
	scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);
        pos[p[i]] = i;
        inv[i] = qpow(i, MOD - 2);
    }
    for(int j = n; j > 0; --j) {
        for(int i = 0; i <= n; ++i)  c[i] = sum[i] = 0;
        for(int t = j + 1; t <= n; ++t) {
            c[pos[t]] = 1;
            sum[pos[t]] = dp[j][t];
        }
        for(int i = n - 1; i >= 0; --i) {
            c[i] += c[i + 1];
            sum[i] = (sum[i] + sum[i + 1]) % MOD;
        }
        for(int i = j - 1; i >= 0; --i) {
            int tot = c[pos[i]];
            int sm = sum[pos[i]];
            if(tot)  dp[i][j] = ((ll) inv[tot] * sm + 1) % MOD;
        }
    }
    int ret = 0;
    for(int i = 1; i <= n; ++i)  ret = (ret + dp[0][i]) % MOD;
    printf("%lld", ((ll) ret * inv[n] % MOD + 1) % MOD);
}