灾祸之二 破坏灾杰·莉洁娜

zrzring 2021-01-13 PM 17℃ 0条

题目链接

对于一个长度为 $n$ 区间选取一个子区间共有 $C(n, 2)$ 种选取的方法,因为等概率选取,所以计算期望可以将所有区间的贡献求和并除以总状态数即可

然后就是计算区间所有贡献的和,一个很自然的想法是线段树维护区间贡献,记录黑白之章往前后的长度与数量,合并答案的时候就可以计算所有黑白之章对的距离和

实际上这个信息是有可减性的,于是可以利用差分将复杂度优化到 $O(n)$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct NODE {
    int cnt[2]; long long dis[2], ans;
} ans[N];

int n, m, cnt, inv[N];

char ch[N];

NODE operator + (const NODE &x, const NODE &y) {
    NODE t;
    t.cnt[0] = x.cnt[0] + y.cnt[0]; t.dis[0] = x.dis[0] + y.dis[0];
    t.cnt[1] = x.cnt[1] + y.cnt[1]; t.dis[1] = x.dis[1] + y.dis[1];
    t.ans = x.ans + y.ans + x.cnt[0] * y.dis[1] - x.dis[0] * y.cnt[1] + x.cnt[1] * y.dis[0] - x.dis[1] * y.cnt[0];
    return t;
}

NODE operator - (const NODE &x, const NODE &y) {
    NODE t;
    t.cnt[0] = x.cnt[0] - y.cnt[0]; t.dis[0] = x.dis[0] - y.dis[0];
    t.cnt[1] = x.cnt[1] - y.cnt[1]; t.dis[1] = x.dis[1] - y.dis[1];
    t.ans = x.ans - y.ans + t.cnt[0] * x.dis[1] - t.dis[0] * x.cnt[1] + t.cnt[1] * x.dis[0] - t.dis[1] * x.cnt[0];
    return t;
}

NODE make(int x, int c) {
    NODE t; t.cnt[c] = 1; t.dis[c] = x; t.cnt[c ^ 1] = 0; t.dis[c ^ 1] = 0; t.ans = 0; return t;
}

int calc(int n) {return 2ll * inv[n] * inv[n + 1] % mod;}

int main() {
    n = read(); m = read(); scanf("%s", ch + 1);
    for (int i = 1; i <= n; i++) ans[i] = ans[i - 1] + make(i, ch[i] - '0');
    inv[1] = 1;
    for (int i = 2; i <= n + 1; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        printf("%d\n", 1ll * (ans[r] - ans[l - 1]).ans % mod * calc(r - l + 1) % mod);
    }
    return 0;
}
Title - Artist
0:00