P7875 「SWTR-07」IOI 2077

本文主要是介绍P7875 「SWTR-07」IOI 2077，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1 P7875 「SWTR-07」IOI 2077

• 题目链接：https://www.luogu.com.cn/problem/P7875

2 题目描述

时间限制 \(1ms\) | 空间限制 \(512MB\)

\(IOI 2077\) 有 \(n\) 位候选参赛者，他们分别编号为 \(1\sim n\)。每位候选参赛者都有一个能力值，且能力值互不相等，第 \(i\) 位候选参赛者的能力值为 \(a_i\) 。小 \(A\) 更喜欢有序的数字，所以他将这 \(n\) 位候选参赛者按照能力值从小到大排好了序，即满足 \(a_i< a_{i+1}, (1\leq i < n)\) 。

正式参赛者将会从这 \(n\) 位候选参赛者中产生。具体地，所有参赛者将是候选参赛者的一个子串 \([l,r]\)，即编号为 \(l,l+1,\cdots,r\) 的选手将参加 \(IOI 2077\)，其中，小 \(A\) 的编号为 \(k\)。因为他知道自己被钦定参加 \(IOI2077\)，所以 \(l\leq k\leq r\) 。可能的参赛者一共有 \(q\) 种情况，每种情况用三个数 \(l_i,r_i,k_i\ (l_i\leq k_i\leq r_i)\) 描述，即参赛者为编号在区间 \([l_i,r_i]\) 中的候选参赛者，而小 \(A\) 的编号为 \(k_i\) 。

由于自己太菜，小 \(A\) 对即将到来的 \(IOI\) 感到力不从心。他决定选择一些参赛者作为队友，并与他们在赛场上相互帮（\(zuo\)）助（\(bi\)）。具体地，设正式参赛人数为 \(s\)，那么小 \(A\) 会在 \([0,\lfloor\frac{s-1}{2}\rfloor]\) 中等概率随机选择一个数 \(m\) ，并从 \(s\) 位参赛者中随机选出 \(2m\) 个作为他的队友。不过，小 \(A\) 不希望自己显得太菜，所以他的能力值 \(a_k\) 必须是这 \(2m+1\) 个人的能力值的中位数。

俗话说，人多力量大，小 \(A\) 希望他与所有选出的队友的能力值之和尽量地大。不过在此之前，他想知道这个值的期望值是多少。请对 \(998244353\) 取模，保证答案在该模数下有意义。对于每一种可能的参赛者情况，你都需计算该情况下的答案。为了避免过大的输出，你只需要计算所有答案的异或和。

数据范围：

对于 \(100\%\) 的数据，\(1\leq n,q\leq 2\times 10^6\) ，\(1\leq l_i\leq k_i\leq r_i\leq n\) ，\(1 \le a_i \le 998244352\) ，\(a_i < a_{i+1}\) \((1 \leq i < n)\)。

3 题解

首先我们发掘性质：

\(k\) 是中位数的意义在于 \(k\) 正好位于这 \(2m + 1\) 个数排序后的中间，由于这里保证给出序列单调递增，所以这 \(2m\) 个数必定有 \(m\) 个在 \([l, k - 1]\)，有 \(m\) 个在 \([k + 1, r]\)。

考虑朴素暴力。

直接枚举询问，对于每个询问枚举所有可能的 \(m\)。

显然，对于给定 \(m, l, r, k\)，总共的选取情况数为 \(\dbinom{k-l}{m}\dbinom{r-k}{m}\)。

考虑此时的总和。

容易发现，设 \(sum_{m, 1}\) 为在 \(k - l\) 中选出 \(m\) 个数求和的所有情况的和，设 \(sum_{m, 2}\) 为在 \(r - l\) 中选出 \(m\) 个数求和的所有情况的和，那么此时的总和为 \(sum_{m, 1} \times \dbinom{r-k}{m} + sum_{m, 2} \times \dbinom{k - l}{m}\)。

此时答案是 \(\dfrac{sum_{m, 1}\times \dbinom{r-k}{m} + sum_{m, 2} \times \dbinom{k - l}{m}}{\dbinom{k-l}{m}\dbinom{r-k}{m}} = \dfrac{sum_{m, 1}}{\dbinom{k-l}{m}} + \dfrac{sum_{m, 2}}{\dbinom{r-k}{m}}\)。

现在，这个 \(sum_{m, 1}\) 和 \(sum_{m, 2}\) 怎么求呢？

考虑区间内每一个数的贡献，即固定选择当前数，看当前数会被选中多少次。

容易发现，固定某个数后，我们只需要在剩下的数中选择 \(m - 1\) 个数即可。而从剩下的数中选择 \(m - 1\) 个数的情况数是固定的，所以此时可以提出这个情况数，剩下的就是一个区间和。

即：\(sum_{m, 1} = (\sum_{i = l}^{k-1} \limits a_i) \times \dbinom{k-l-1}{m-1}, sum_{m, 2} = (\sum_{i=k+1}^r \limits a_i) \times \dbinom{r-k-1}{m-1}\)。

而这个 \(\sum_{i=l}^{k-1} \limits a_i\) 和 \(\sum_{i=k+1}^r \limits a_i\) 可以用前缀和维护。

此时，对于某一个 \(m\) 答案就是：

\(\dfrac{(\sum_{i = l}^{k-1} \limits a_i) \times \dbinom{k-l-1}{m-1}}{\dbinom{k-l}{m}} + \dfrac{(\sum_{i=k+1}^r \limits a_i) \times \dbinom{r-k-1}{m-1}}{\dbinom{r-k}{m}}\)

我们这里用 \(O(\log_2n)\) 处理出两个分母的逆元，加上枚举的时间复杂度，总时间复杂度是 \(O(nq\log_2n)\)。

运气好的话可以拿到 \(61\space pts\)，但显然这是不够的。

注意到这里上下两部分的组合数长的很像，拆开发现：

\[\dbinom{k-l-1}{m-1} = \dfrac{(k-l-1)!}{(m-1)!\space (k-l-m)!} \]

\[\dbinom{k-l}{m} = \dfrac{(k-l)!}{m!\space (k-l-m)!} \]

\[\dfrac{\dbinom{k-l-1}{m-1}}{\dbinom{k-l}{m}} = \dfrac{\dfrac{(k-l-1)!}{(m-1)!\space (k-l-m)!}}{\dfrac{(k-l)!}{m!\space (k-l-m)!}} = \dfrac{(k-l-1)!}{(m-1)!\space (k-l-m)!} \times \dfrac{m!\space (k-l-m)!}{(k-l)!}=\dfrac{m}{k-l} \]

那么，对于一个 \(m\) 的答案就是：

\(\sum_{i=l}^{k-1}\limits a_i \times \dfrac{m}{k-l} + \sum_{i=k+1}^r \limits a_i \times \dfrac{m}{r-k}\)

容易发现，枚举的 \(m\) 的下界是 \(0\)，上界 \(up\) 是 \(\min\{\lfloor \dfrac{r-l}{2} \rfloor,k-l, r-k\}\)。

那么此时，对于一个询问的答案就是：

\(\sum_{m = 1}^{up} \limits (\sum_{i=l}^{k-1}\limits a_i \times \dfrac{m}{k-l} + \sum_{i=k+1}^r \limits a_i \times \dfrac{m}{r-k})\)

容易发现两部分可以分开计算，所以此时答案为：

\(\sum_{i=l}^{k-1}\limits a_i \times\sum_{m=1}^{up} \limits \dfrac{m}{k-l} + \sum_{i=k+1}^r \limits a_i \times \sum_{m=1}^{up}\limits \dfrac{m}{r-k}\)

把 \(\dfrac{1}{k-l}\) 和 \(\dfrac{1}{r-k}\) 提出来，就变成了一个等差数列求和公式：

\(\dfrac{\sum_{i=l}^{k-1}\limits a_i}{k-l} \times \dfrac{up(up+1)}{2} + \dfrac{\sum_{i=k+1}^r \limits a_i}{r-k} \times \dfrac{up(up + 1)}{2}\)。

因此，我们只需要线性预处理逆元和前缀和，然后枚举所有询问，直接回答即可。

别忘了把 \(a_k\) 的值记到贡献里面，并把答案除以 \(\dfrac{\lfloor r-l \rfloor}{2} + 1\)，得出期望。

时间复杂度 \(O(n)\)，可以通过本题。

4 代码（空格警告）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N = 2e6 + 10, mod = 998244353;
#define int long long
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int t, n, q, ans1, ans, up;
int a[N], l[N], r[N], k[N], sum[N];
int inv[N];
void init()
{
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - (mod / i * inv[mod % i] % mod)) % mod;
}
int S(int x, int y) {return ((sum[y] - sum[x - 1]) % mod + mod) % mod;}
signed main()
{
    t = read();
    n = read(), q = read();
    init();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= q; i++) l[i] = read(), r[i] = read(), k[i] = read();
    for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + a[i]) % mod;
    for (int i = 1; i <= q; i++)
    {
        up = min((r[i] - l[i]) / 2, min(k[i] - l[i], r[i] - k[i]));
        ans1 = (a[k[i]] * (up + 1)) % mod;
        ans1 = (ans1 + (S(l[i], k[i] - 1) * (up * up % mod + up)) % mod * inv[2] % mod * inv[k[i] - l[i]] % mod) % mod;
        ans1 = (ans1 + (S(k[i] + 1, r[i]) * (up * up % mod + up)) % mod * inv[2] % mod * inv[r[i] - k[i]] % mod) % mod;
        ans1 = ans1 * inv[(r[i] - l[i]) / 2 + 1] % mod;
        ans = (ans ^ ans1);
    }
    printf("%lld", ans % mod);
    return 0;
}

欢迎关注

这篇关于P7875 「SWTR-07」IOI 2077的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！