2021牛客暑期多校训练营#1:I-Increasing Subsequence

I-Increasing Subsequence

原题链接：https://ac.nowcoder.com/acm/contest/11166/I

题目大意

Ailce 和 Bob 在一个大小为$n(1\le n\le 5000)$的排列$P$上玩游戏，双凤轮流选择数字。

每一轮中，当前玩家需要选择一个比之前双方选择过的元素都大的元素。并且，如果当前玩家之前选择了$P_i$,当前回合选择了$P_j$,则必须满足$j>i$.若有多种选择，则将等概率地随机选择一个合法的元素。

第一个回合的玩家会随机选择一个数，第二个回合的玩家会随机选择一个比第一个回合选择的大的元素。没有合法操作时游戏结束。

求游戏结束时，双方的总回合数期望，得数对$998244353$取模。

解题思路

思考动态规划，使用期望dp.

使用快速幂预先处理逆元，以第一维度表述己方上次的选择，第二维度表述对方.

当$p_x<p_y$:
可得转移方程：$$dp[i][j]=1+\frac{1}{c}\sum _{k>x,p_k>p_y}dp[k][y]$$
当$p_x<p_y$
可得方程：$$dp[i][j]=1+\frac{1}{c}\sum _{k>y,p_k>p_x}dp[x][y]$$

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353,N=5050;
ll pm(ll x){
    ll sum=1,ss=mod-2,d=x;while(ss){
    if(ss&1)sum*=d,sum%=mod;d*=d;d%=mod;ss>>=1;}return sum;
}
int a[N],n;
ll inv[N],dp[N][N],cnt[N],sum[N],ans;
int main()
{
    inv[0]=1;for(int i=1;i<N;i++)inv[i]=pm(i);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n;i>=1;i--){
    ll s,c;s=c=0;for(int j=n;j>=0;j--){
    if(i==j)continue;if(a[i]>a[j]){
    dp[i][j]=(s*inv[c]+1)%mod;sum[j]+=dp[i][j];sum[j]%=mod;cnt[j]++; }else{
    dp[i][j]=(sum[j]*inv[cnt[j]]+1)%mod;s+=dp[i][j];s%=mod;c++;}} }for(int i=1;i<=n;i++)ans=(ans+dp[i][0])%mod;printf("%lld",(ans*inv[n])%mod); 
}