【牛客竞赛】Increasing Subsequence题解

题目大意

给定一个 $n$ 个数的排列 $a$（从1到n，每个数都会出现且仅有一次），Alice和Bob轮流选一个数，Alice先选。

每次选数需要满足以下要求：

• 当前选的数必须在当前选数的人上次选的数的右面。
• 当前选的数的大小，必须比 所有人选出来的数 要大。

如果有多个数同时满足要求，那么每个数被选的概率是均等的。

求两人进行选数的期望次数，如果结果是 $A/B$，那么就写成 $A \times B^{998244351} \bmod 998244353$ 的形式。

原题来自牛客竞赛

思路

1. 这种题目一看就是期望DP，那么我们第一步就显然是设计状态，我们可以利用把它转化为”拓扑图”的那种思路，即：

   • 找到所有的结束状态
   • 建立各个状态的联系
   • 从结束状态往前递推

   那么这道题的结束状态无非是两种情况：1.当前取到的数是最大的 2.当前取到的数是最右边的数。

   也就是说，我们在不同关系的转移的时候，就要以这两个为转移的起点。

   我们注意到了以下几点:

   • 每个人取数的位置只需要在这个人上一次取的数的右边，即影响可能的结果的位置因素只有这一个。
   • 这是一个排列，即数组下标代表的数字与下标形成的集合是一样的。

   那么我们不妨设 f[i][j]代表当前取的数字大小是 $i$，下一个取的数字大小是 $j$ 时，选数操作的期望次数。

2. 设置转移方程

   我们设 $pos[i]$ 表示数字 $i$ 出现在序列的位置。根据上文提到的内容，$f[i][j] \to f[j][k]$，要满足 $k > j$ 且 $pos[k] > pos[i]$。（注意 $i < j$，所以不用对比 $k$ 和 $i$ 的大小了）。

   事实上，我们在进行循环转移的时候，不用专门设置pos数组，只需按照 $a[n] \to a[1]$ 的顺序，记录一下当前满足 $k > j$ 且 $pos[k] > pos[i]$ 的数的个数，然后进行转移。（一些细节会写在代码注释中）

代码

一些细节

• 1部分是转移的重点部分，其中sum表示 如果当前位置为i，且i可以被选的话，那么之后的序列为它提供的期望长度，cnt表示当前比j要大的数的个数，即选了j之后，还可以选哪些。
• 这个dp的过程其实就是 向后统计，向前转移，dp顺序的第一次循环是按照数的大小来的，它是从n到1的，而第二个循环是按照数字的位置来的（注意与状态f[i][j]的含义做区分）。
• 我们在转移的时候，因为这次选的数大小为j，那么下次选的数只需要比j大即可。所以我们可以直接把它加入到sum中（向后统计），进而去下一步的转移（向前转移）。我们不需要担心在j之后选的数会在 $pos[a[i]]$ 之前，因为每次往 $f[a[i]][j]$ 转移的时候，当前加入到sum中的数都在 $pos[a[i]]$ 的右边（前面的数还没有被统计到）。（这就是为什么我们把位置循环放在了第二层循环）

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 5005, mod = 998244353;
const double eps = 1e-7;
typedef long long ll;

ll a[maxN], inv[maxN], f[maxN][maxN];
ll n;

ll qsm(ll a,ll n){
    ll res = 1;
    while(n){
        if(n&  1) res = (ll) res *a % mod;
        a=(ll)a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        inv[i] = qsm(i, mod - 2);
    for(int j = n; j >= 0; --j) { //1
        ll cnt = 0, sum = 0;
        for(int i = n; i >= 0; --i) { //向后统计
            if(a[i] > j) {
                ++cnt;
                sum = (sum + f[j][a[i]]) % mod;
            }
            else if(a[i] < j) { //往前递推
                f[a[i]][j] = 1;
                if(!cnt)
                    continue;
                f[a[i]][j] = (f[a[i]][j] + sum * inv[cnt] % mod) % mod;
            }
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; ++i)
        res = (res + f[0][i]) % mod;
    res = (res * inv[n]) % mod;
    printf("%lld\n", res);
    return 0;
}