Submission #59942489

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/segtree>

#define int long long

using namespace std;
using namespace atcoder;

const int N = 2e5 + 10;
const int MOD = 998244353;
const int inv2 = 499122177;

int n, k, p[N];

int op (int a, int b) {
    if (a + b >= MOD) return a + b - MOD;
    return a + b;
}

int e() { return 0; }

int qpow (int x, int p) {
    int res = 1;
    while (p) {
        if (p % 2) res = res * x % MOD;
        x = x * x % MOD;
        p /= 2;
    }
    return res;
}

int inv(int x) {
    return qpow(x, MOD - 2);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    int bas = 0;
    {segtree<int, op, e> seg(n);
    for (int i = 0; i < n; i++) {
        bas += seg.prod(p[i], n);
        seg.set(p[i], 1);
    }}
    int res = 0, sub = 0, add = (k * (k - 1) / 2LL) % MOD;
    add = add * inv2 % MOD;
    segtree<int, op, e> seg(n);
    for (int i = 0; i < k; i++) {
        (sub += seg.prod(p[i], n)) %= MOD;
        seg.set(p[i], 1);
    }
    for (int i = k; i <= n; i++) {
        int cur = (MOD + bas + add - sub) % MOD;
        (res += cur) %= MOD;
        if (i == n) break;
        seg.set(p[i - k], 0);
        (sub += (MOD - seg.prod(0, p[i - k]))) %= MOD;
        (sub += seg.prod(p[i], n)) %= MOD;
        seg.set(p[i], 1);
    }
    (res *= inv(n - k + 1)) %= MOD;
    cout << res << endl;
    return 0;
}

Submission Info

Judge Result