跃迁引擎启动

2019 计蒜之道复赛 A 外教 Michale 变身大熊猫

发表于 更新于 分类于 ， 阅读次数：

题面

给定一个长度为 $n$ 的序列 $a$，等概率选择一个他的最长上升子序列，求每个位置被选到的概率。

其中 $1 \le n \le 10^5$。

分析

考虑如何求最长上升子序列的个数，令 $dp(i)$ 表示最长上升子序列最后一个数为 $i$ 时的长度和方案数二元组。

两个二元组合并时，若长度相同，则方案数相加，否则选一个长度大的。

对于位置 $a_i$，在询问小于 $a_i$ 的 $dp$ 信息和，将这个信息和的长度加一后，更新 $a_i$ 开始的后缀中每一个位置的信息。

树状数组加速即可。

回到原题。

我们对于每个前缀求出最长上升子序列的信息，和对应每个后缀的最长上升子序列信息。

每一个位置的概率的分母为总方案数，若其前缀和后缀的 LIS 长度相加再加一等于总体的 LIS 长度，那么选择它的方案数就是两个部分方案数的乘积，否则方案数为 0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 600000 + 5;

ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}
ll inv(ll x) {
    return qpow(x, mod - 2);
}

int n, nn, a[maxn];
vector<int> lsh;

PII info[maxn];
PII add(PII a, PII b) {
    if (a.first == b.first) return { a.first, (a.second + b.second) % mod };
    else if (a.first > b.first) return a;
    else return b;
}
inline int lowbit(int x) {
    return x & -x;
}
inline void update(int i, PII x) {
    for (; i <= nn; i += lowbit(i)) {
        info[i] = add(info[i], x);
    }
}
inline PII query(int i) {
    PII r = { 0, 1 };
    for (; i; i -= lowbit(i)) {
        r = add(r, info[i]);
    }
    return r;
}

PII pre[maxn], suf[maxn];
ll ans[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), lsh.push_back(a[i]);
    sort(lsh.begin(), lsh.end());
    lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
    nn = (int)lsh.size();
    for (int i = 1; i <= n; i++) a[i] = lower_bound(lsh.begin(), lsh.end(), a[i]) - lsh.begin() + 1;

    for (int i = 1; i <= n; i++) {
        PII x = query(a[i] - 1);
        pre[i] = x;
        x.first++;
        update(a[i], x);
    }

    PII sum = query(nn);
    int len = sum.first;
    ll fm = inv(sum.second);
    
    for (int i = 1; i <= nn; i++) info[i] = { 0, 0 };
    for (int i = n; i >= 1; i--) {
        a[i] = nn - a[i] + 1;
        PII x = query(a[i] - 1);
        suf[i] = x;
        x.first++;
        update(a[i], x);
    }

    for (int i = 1; i <= n; i++) {
        if (pre[i].first + suf[i].first + 1 == len) {
            ll fz = 1ll * pre[i].second * suf[i].second % mod;
            printf("%lld ", fz * fm % mod);
        } else printf("0 ");
    }
    return 0;
}