Increasing Subsequence

2021-07-30

字数统计: 1.3k字 | 阅读时长≈ 5分

题目大意

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

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

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

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

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

原题来自牛客竞赛

思路

这种题目一看就是期望DP，那么我们第一步就显然是设计状态，我们可以利用把它转化为“拓扑图”的那种思路，即：
- 找到所有的结束状态
- 建立各个状态的联系
- 从结束状态往前递推
那么这道题的结束状态无非是两种情况：1.当前取到的数是最大的 2.当前取到的数是最右边的数。

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

我们注意到了以下几点:
- 每个人取数的位置只需要在这个人上一次取的数的右边，即影响可能的结果的位置因素只有这一个。
- 这是一个排列，即数组下标代表的数字与下标形成的集合是一样的。
那么我们不妨设 f[i][j]代表当前取的数字大小是i，下一个取的数字大小是j时，选数操作的期望次数。
设置转移方程

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

事实上，我们在进行循环转移的时候，不用专门设置pos数组，只需按照a[n] ->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);  //预处理出除以1,2,3,4的结果（因为题目要求是转化为乘法）
    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; //此时f[a[i]][j]第一次被更新到，那么它初始期望长度就是1
                if(!cnt) //假如在当前位置，向后统计的时候，存在选了j之后还可以被选的数，
                    continue; //那么就能更新f[a[i]][j]的期望长度(毕竟可以继续往后选了嘛)，如果没有，那就跳过。
                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;//每个数作为第一次被选的可能性都为1/n.
    printf("%lld\n", res);
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/07/30/Increasing-Subsequence/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！