题解：P7099 [yLOI2020] 灼

· · 题解

题意

给定 n 个陷阱（坐标 x_i），q 只穿山甲在这些陷阱之间（坐标 y_i，按从小到大顺序给出，穿山甲与陷阱在同一坐标就会被抓住）等概率向左或向右随机游走，救援队问你他们穿山甲期望多久会被陷阱抓住，以确认他们的决策。

高斯消元做法

我们把坐标 y 时期望设成 f_i，得出 f_i = \frac{1}{2}(f_{i - 1} + f_{i + 1}) + 1，这就导致转移出现环，移向得 \frac{1}{2}f_{i - 1} - f_i + \frac{1}{2}f_{i + 1} = -1。

直接用高斯消元是 \operatorname{O}(n^3 + q) 的，能拿 50 分，而由于矩阵中只有 f_{i - 1},f_i,f_{i + 1},f_{V + 1} 不为 0，考虑从上往下消元时只需要消下一行和上一行，可以得到 \operatorname{O}(n\log n + q) 或 \operatorname{O}(n + q) 的做法并得到 70 分。

打表与结论

这个时候套路已经结束，此时可以试图用 70 分做法找结论，可以发现若穿山甲在距离为 d 的两个陷阱之间，里较近的陷阱距离为 k 时答案为 k(d - k + 1)。

证：

由于 \frac{1}{2}f_{i - 1} - f_i + \frac{1}{2}f_{i + 1} = -1，乘上 2 得到 f_{i - 1} - 2f_i + f_{i + 1} = -2，即 (f_{i + 1} - f_i) - (f_i - f_{i - 1}) = -2，也就是说二阶差分固定，又因为零点为整点，故一阶差分为一次函数 y = -2x。

我们知道一阶差分为一次函数时原数组求积可得到二次函数，这就意味着 f_i = ak^2 + bk + c，可以解得 a = -1。

我们将 k 的定义范围扩展为到其中一点的距离，不需要最小，在 k = 0 与 k = l + 1 时得到取值为 0，解得 f_i = -k(k - l - 1) = k(l - k + 1)，注意原题需要取模，这样问题就解决了。

code

#include<bits/stdc++.h>
using namespace std;
int n,q,x[100009],pl[5000009],f[100009][4];//f[i][0] = g[i][i - 1],f[i][1] = g[i][i],f[i][2] = g[i][i + 1],f[i][2] = g[i][N + 1];
const int mod = 998244353;
int fp(int x,int y){
    if(x == 0)
        return 0;
    if(y == 0)
        return 1;
    int t = fp(x,y >> 1);
    t = 1ll * t * t % mod;
    if(y & 1)
        t = 1ll * t * x % mod;
    return t;
}
int main(){
    scanf("%*d %d %d",&n,&q);
    for(int i = 1; i <= n; i ++){
        scanf("%d",&x[i]);
    }
    sort(x + 1,x + n + 1);
    if(x[n] <= 100000){//这里时70分部分分部分，赛场上用 if 将对应部分分分开处理有利于防掉大分。
        for(int i = x[1]; i <= x[n]; i ++){
            int o = lower_bound(x + 1,x + n + 1,i) - x;
            if(x[o] == i){
                f[i][1] = 1;
            }
            else{
                f[i][0] = (mod + 1) >> 1,f[i][1] = mod - 1,f[i][2] = (mod + 1) >> 1,f[i][3] = mod - 1;
            }
        }
        for(int i = x[1]; i < x[n]; i ++){
            int d = fp(f[i][1],mod - 2);
            f[i][1] = 1ll * d * f[i][1] % mod;
            f[i][2] = 1ll * f[i][2] * d % mod;
            f[i][3] = 1ll * f[i][3] * d % mod;
            //printf("%d %d %d %d\n",f[i][0],f[i][1],f[i][2],f[i][3]);
            f[i + 1][3] = (mod + f[i + 1][3] - 1ll * f[i + 1][0] * f[i][3] % mod) % mod;
            f[i + 1][1] = (mod + f[i + 1][1] - 1ll * f[i + 1][0] * f[i][2] % mod) % mod;
            f[i + 1][0] = 0;
        }
        for(int i = x[n]; i > x[1]; i --){
            int d = fp(f[i][1],mod - 2);
            f[i][1] = 1ll * d * f[i][1] % mod;
            f[i][3] = 1ll * d * f[i][3] % mod;
            f[i - 1][3] = (mod + f[i - 1][3] - 1ll * f[i][3] * f[i - 1][2] % mod) % mod;
            f[i - 1][2] = 0;
        }
        int a = 0,b = 0,c = 0,d = 0x3f3f3f3f;
        for(int i = 1; i <= q; i ++){
            int y = 0;
            scanf("%d",&y);
            //printf(" %d\n",f[y][3]);
            a = a ^ f[y][3];
            b = b + (f[y][3] & 1);
            c = max(c,f[y][3]);
            d = min(d,f[y][3]);
        }
        printf("%d\n%d\n%d\n%d\n",a,b,c,d);
    }
    else{
        int l = 1;
        long long a = 0,b = 0,c = 0,d = 9e18;
        for(int i = 1; i <= q; i ++){
            int y;
            long long ret;
            scanf("%d",&y);
            while(x[l + 1] <= y)
                l++;
            if(y == x[l])
                ret = 0;
            else{
                int k = min(y - x[l],x[l + 1] - y);
                int fl = x[l + 1] - x[l] - 1;
                ret = 1ll * k * (fl - k + 1);
            }
            ret = ret % 998244353;
            a = a ^ ret;
            b += ret & 1;
            c = max(c,ret);
            d = min(d,ret);
        }
        printf("%lld\n%lld\n%lld\n%lld\n",a,b,c,d);
    }
    return 0;
}