题意

题目链接。

数轴上有 $n$ 个虫洞，有 $q$ 个按坐标升序给出的飞船，保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格，对于每个飞船，求到达任意一个虫洞的期望时间。

解析

记 $f_i$ 为位置在 $i$ 的飞船的期望时间，只要 $i$ 位置没有虫洞（有虫洞期望时间显然为 $0$），就有 $f_i=1+\frac{1}{2}(f_{i-1}+f_{i+1})$，化简得 $(f_{i+1}-f_i)-(f_i-f_{i-1})=-2$，即其二阶差分为一定值，由此可知 $f_i$ 为一个二次函数。将 $f_x=ax^2+bx+c$ 代入上式，可得其二次项系数为 $-1$。

由于飞船一定在两个虫洞之间，记这两个虫洞的位置分别为 $x_1$ 和 $x_2$，我们得到了这个二次函数的两个零点，结合求出的二次项系数可以写出零点式：$f_x=-(x-x_1)(x-x_2)$。

由于飞船坐标升序给出，每个飞船在哪两个虫洞之间是易于维护的，本题解决。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int M=5e6+5;
const int mod=998244353;
int T,n,q,x[N],y[M];
int ANS,ansji,ansmx=-1,ansmn=1e9;
signed main(){
    scanf("%lld",&T);scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
    sort(x+1,x+1+n);int now=2;//对 x 进行排序
    if(n==1) x[2]=x[1];//特判 n=1
    for(int i=1,y;i<=q;i++){
        scanf("%lld",&y);
        while(y>x[now]) now++;//更新现在在哪两个虫洞之间
        int ans=-(y-x[now-1])*(y-x[now])%mod;//带入公式
        ANS^=ans;if(ans&1) ansji++;
        ansmx=max(ansmx,ans);ansmn=min(ansmn,ans);
    }
    printf("%lld\n%lld\n%lld\n%lld",ANS,ansji,ansmx,ansmn);
    return 0;
}