自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:26:37，当前版本为作者最后更新于2020-11-22 12:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

F

Algorithm 1

对于虫洞间距离不超过 $2$ 的情况，显然答案只有 $0$ 和 $1$ 两种可能。期望得分 $20$ 分。

Algorithm 2

考虑推一推式子。设 $f_i$ 表示在坐标 $i$ 时的期望步数，那么转移显然：

这个式子的意思是分别有 $\frac 1 2$ 的概率向左走向右走，然后变为对应坐标的期望步数。同时因为走了一步，所以最后要 $+1$。

边界条件是在虫洞结点上 $f_i = 0$。

对于子任务 $3$，可以通过手算发现这时候不在虫洞上的 $f$ 的值为 $2$。结合算法一，期望得分 $30$ 分。

Algorithm 3

用高斯消元求解算法二中的式子，时间复杂度 $O(qn^3)$，期望得分 $50$ 分。

Algorithm 4

验题人拉瓦手算带入消元得到了一个递推式，可以矩阵加速，时间复杂度 $O(q \log n)$ 带 $8$ 倍常数。期望得分 $70$ 分。

Algorithm 5

考虑把算法二中的式子乘二然后整理，可以得到

这就是说，$f$ 的二阶差分是一个非零常数。因此 $f$ 的通项公式一定是一个二次多项式。

我们考虑正着推式子：对于 $g(x) = ax^2 + bx + c$，有 $g(x - 1) = a(x^2 - 2x + 1) +b(x - 1) + c$，$g(x + 1) = a(x^2 + 2x + 1) +b(x + 1) + c$。

因此 $g(x) - g(x - 1) = 2ax - a + b$；$g(x + 1) - g(x) = 2ax + a + b$。

因此 $[g(x + 1) - g(x)] - [g(x) - g(x - 1)] = 2a$。这就是说，二次函数的二阶差分值是其二次项系数的两倍。因此可以得到 $f$ 的通项公式的二次项系数是 $-1$。同时我们还知道 $f$ 的两个零点，因此可以直接以零点式写出 $f$ 的通项公式，带入 $x$ 即可 $O(1)$ 计算。时间复杂度 $O(n \log n + q)$。这里的 $\log n$ 需要对 $x$ 数组进行排序。然后用指针指向第一个大于询问值的元素。因为询问是单调不降的，所以指针移动是均摊 $O(1)$ 的。期望得分 $100$ 分。

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>

template <typename T>
inline void qr(T &x) {
  char ch = getchar(); x = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

const int maxn = 100005;
const int mod = 998244353;


int n, q;
int ans, answ, answe = -1, answer = mod + 1; 
int a[maxn];

int main() {
  qr(n); qr(n); qr(q);
  for (int i = 1; i <= n; ++i) {
    qr(a[i]);
  }
  std::sort(a + 1, a + 1 + n);
  for (int x, p = 1; q; --q) {
    qr(x);
    while ((p < n) && (a[p] <= x)) ++p;
    int y = 1ll * (x - a[p - 1]) * (a[p] - x) % mod;
    ans ^= y;
    if (y & 1) ++answ;
    answe = std::max(answe, y);
    answer = std::min(answer, y);
  }
  std::cout << ans << std::endl << answ << std::endl << answe << std::endl << answer << std::endl;
}