DDOSvoid's Blog

牛客练习赛98 E Robotic Girl

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11188/E

简要题意：现在有一个长度为 $n$ 的序列 $a_i$，定义 $F_0(l,r)$ 为区间 $[l,r]$ 内的逆序对个数，同时 $F_k(l,r)=\sum_{i=l}^r\sum_{j=i}^rF_{k-1}(i,j)$，给定 $k$，求 $F_k(1,n)$

$n\le 3\times 10^5$

Solution

观察 $F_k(l,r)=\sum_{i=l}^r\sum_{j=i}^rF_{k-1}(i,j)$，容易发现这个东西类似于前缀和

我们考虑一个逆序对 $(x,y)$，它对 $F_k(l,r)$ 的贡献是相当与令 $a_y=1$，同时向后做 $k+1$ 次前缀和到 $r$ 的答案乘上令 $a_x=1$，同时向前做前缀和到 $l$ 的答案，那么就是 $\binom{r-x+k}{k}\times\binom{x-l}{k}$，这些东西用树状数组维护即可

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
#include <iostream>
#include <algorithm>
#define maxn 300010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

const int p = 998244353;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }

int n, m, a[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) 
        a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}

struct Fenwick { 
    int Bit[maxn];
    
    void add(int i, int v) { while (i <= cnt) Bit[i] = ::add(Bit[i], v), i += lowbit(i); }
    int get_sum(int i) {
        int s = 0;
        while (i) s = ::add(s, Bit[i]), i -= lowbit(i);
        return s; 
    }
    void clear() { for (int i = 1; i <= cnt; ++i) Bit[i] = 0; }
} B;

ll fac[maxn * 2], inv[maxn * 2];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }

void work() {
    cin >> n >> m; ++m; ll ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init_hash(); B.clear();
    for (int i = n; i; --i) {
        B.add(a[i], C(n - i + m - 1, m - 1));
        ans = (ans + B.get_sum(a[i] - 1) * C(i - 1 + m - 1, m - 1)) % p;
    } cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; init_C(600000);
    while (T--) work(); 
    return 0;
}