Increasing Subsequence

题目描述

给出排列P，两个人轮流取数，每次取的数需要在之前该人取数的右边，且比当前取出来所有的数都要大。所有当前可选的数都将等概率随机的被当前决策人选中。问两个人期望取数的轮数。

范围

\(n \leq 5000\)

题解

概率dp，设\(f_{i,j}\)表示第一个人上一步选了\(a_i\)，第二个人选了\(a_j\)，当前的答案。

• \(a_i > a_j\)

\(f_{i,j} = 1 + {1 \over c} \times \sum_{k > j,a_k > a_i} f_{i,k}\)

• \(a_i < a_j\)

\(f_{i,j} = 1 + {1 \over c} \times \sum_{k > i,a_k > a_j} f_{k,j}\)

注意到计算时可以使用前缀和优化，复杂度\(O(n^2)\)

代码

#include 
using namespace std;
const int N = 5010;
const int mod = 998244353;
#define ll long long
int pow_mod(int a,int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res % mod;
}
ll f[N][N];
ll sum[N];
int inv[N];
int a[N];
ll cnt[N];
int main () {
	int n;
	cin >> n;
	for(int i = 1;i <= n; ++i) {
		cin >> a[i];
	}
	for(int i = 1;i <= n; ++i) {
		inv[i] = pow_mod(i,mod - 2);
	}
	
	for(int i = n;i >= 1; --i) {
		ll s = 0;
		ll c = 0;
		for(int j = n;j >= 0; --j) {
			if(i == j) continue;
			if(a[i] > a[j]) {
				f[i][j] = (1 + s * inv[c]) % mod;
				sum[j] = (sum[j] + f[i][j]) % mod;
				cnt[j] ++;
			}
			else {
				f[i][j] = (1 + sum[j] * inv[cnt[j]]) % mod;
				s = (s + f[i][j]) % mod;
				c ++;
			}
		}
	}
	ll ans = 0;
	for(int i = 1;i <= n; ++i) {
		ans = (ans + f[i][0]) % mod;
	}
	cout << 1ll * ans * inv[n] % mod << endl;
	return 0;
}