题解：P15463 【MX-X25-T7】『FeOI-5』三角晶体

WorldMachine · 2026-03-04 16:50:32 · 题解

你们铁 OI 出的什么题啊 [火][火][火]

下面可能有若干 \mathbb E[X] 直接写成 X 的情况，嗯。

设 D_{n,u}=\displaystyle\sum_{i=1}^n\text{dis}(u,i)，答案即为 \operatorname{ans}_n=\dfrac12\displaystyle\sum_{i=1}^nD_{n,i}=\operatorname{ans}_{n-1}+D_{n-1,n}。

首先注意到，不论图形如何生长，所有的 n 个点永远都在图形的外层边界上，且最外层边界永远是一个长度为 n 的简单环。

加入一个点 n+1 之后显然不会影响之前点的最短路，设 n+1 和点 x,y 连边，那么有 \text{dis}(n+1,i)=\min(\text{dis}(x,i),\text{dis}(y,i))+1，又因为 x,y 相连，有 |\text{dis}(x,i)-\text{dis}(y,i)|\le 1，原式化为：

也就是说：

那么每次相当于在长度为 n 的环上选一条边，选中的两个端点的 D 之和期望为 \dfrac 1n\displaystyle\sum_{i=1}^n(D_{n,u_i}+D_{n,v_i})=\dfrac 2n\sum_{i=1}^n D_{n,i}=\dfrac 4n\operatorname{ans}_n，因此第一个求和式等于 \dfrac2n\operatorname{ans}_n。

考虑第二个求和式，计算距离相等的点对数，设 F(x,y)=\displaystyle\sum_{i=1}^n[\text{dis}(x,i)=\text{dis}(y,i)]，E(x,y)=\displaystyle\sum_{i=1}^n[\min(\text{dis}(x,u_i),\text{dis}(y,u_i))=\min(\text{dis}(x,v_i),\text{dis}(y,v_i))]；定义 A_n 表示有多少个点边对 (x,(u,v)) 满足 \text{dis}(x,u)=\text{dis}(x,v)，B_n 表示有多少个边边对（有序）((x,y),(u,v)) 满足 \min(\text{dis}(x,u),\text{dis}(y,u))=\min(\text{dis}(x,v),\text{dis}(y,v))。

在 (x,y) 外围添加点 n+1 后，原本的外围边 (x,y) 会被两条边 (x,n+1) 和 (n+1,y) 替代，考虑点 i 的贡献变化：

1. 原本 i 到 x,y 距离相等，贡献为 1；那么到 n+1 距离不和到 x,y 距离相等（必定加 1），贡献为 0，这样的点有 F(x,y) 个；
2. 原本 i 到 x,y 距离不等，贡献为 0；由于差不超过 1，原本较远的那个距离就和到 n+1 的距离相同，贡献为 1，这样的点有 n-F(x,y) 个。

因此这部分的贡献变化量为 n-2F(x,y)，随机选择一条边 (x,y)，期望为 n-\dfrac 2nA_n。

同时，n+1 还会对其它外围边产生贡献，由定义易得，这部分贡献恰好就是满足 \min(\text{dis}(x,u),\text{dis}(y,u))=\min(\text{dis}(x,v),\text{dis}(y,v)) 的边 (u,v) 个数，随机选择一条边 (x,y)，期望为 \dfrac{B_n}{n}。因此有：

同理，对于 B_n，原本的边 (x,y) 被替换为 (x,n+1) 和 (n+1,y) 后，考虑边 (u,v) 的贡献变化：

1. 原本 (u,v) 到 x,y 距离相等（边到点的距离定义为两个顶点距离的 \min），贡献为 1；那么到 n+1 的距离不和到 x,y 的距离相等（写出定义式来，发现也必定加 1），贡献为 -1，这样的边有 E(x,y) 条；
2. 原本 (u,v) 到 x,y 距离不等，贡献为 0；由于差不超过 1，写出定义式可以发现，到 n+1 的距离就等于原本较远的那个距离，贡献为 1，这样的边有 n-1-E(x,y) 条。

因此这部分的贡献变化量为 n-1-2E(x,y)，随机选择一条边 (x,y)，期望为 n-1-\dfrac 2nB_n。

考虑新边 (x,n+1) 和 (n+1,y) 对旧边 (u,v) 的贡献，发现 \min(\text{dis}(x,u),\text{dis}(n+1,u))=\text{dis}(x,u)，另一边同理，所以这部分贡献完全只和 x,y 有关，恰好就是 A_n 的定义。由于对每条外围边 (x,y) 求和，每个点被统计两次，这部分贡献的期望就是 \dfrac 2nA_n。

同时原本边 (x,y) 的贡献消失了，这部分的期望是 \dfrac{B_n}n，因此我们有：

两侧同时乘上 n，我们得到了如下递推关系：

猜测这两货都是关于 n 的二次多项式，待定系数法带进去匹配系数，解得 A_n=\dfrac{n^2}3-\dfrac4{15}n，B_n=\dfrac{n^2}3-\dfrac7{15}n，但这个通式仅当 n\ge 5 时才是对的，因为推的过程中会遇到一个 (n-4) 因子，n=4 时就乘 0 了，把 n\le 4 的答案特判掉就行。

那么 F(x,y) 的期望为 \dfrac{A_n}n=\dfrac n3-\dfrac4{15}，代回 \text{ans}_n 的递推式中，我们得到：

直接递推即可，时间复杂度为 \mathcal O(n)。不给固定模数是有什么心事吗。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef unsigned long long ll; typedef __uint128_t lll;
struct { ll m, p; void init(int P) { m = ((lll)1 << 64) / (p = P); } il ll operator()(ll x) { return x -= ((lll)x * m >> 64) * p, x - (x >= p ? p : 0); } } mod;
constexpr int N = 1e6 + 5; int n, p, inv[N], ans[N], Ans;
int main() {
    cin >> n >> p, mod.init(p), ans[4] = 7, ans[5] = 13;
    inv[1] = 1; for (int i = 2, _n = max(n, 15); i <= _n; i++) inv[i] = mod(ll(p - p / i) * inv[p % i]);
    for (int i = 5; i < n; i++) ans[i + 1] = mod(mod((ll)ans[i] * inv[i]) * (i + 2) + (10ll * i - 2) * inv[15]);
    for (int i = 4; i <= n; i++) Ans ^= ans[i]; cout << Ans;
}