P15463 【MX-X25-T7】『FeOI-5』三角晶体
题目描述
刚开始有一个三角形，每秒会出现一个点，它会等概率随机地和目前图形最外围的相邻某两个点连边。
所有点有标号，所有边都是无向边，边权为 $1$。
输入 $n$，对于每个 $k\in[4,n]$ 求出图形生长到有恰好 $k$ 个点后两点间最短路的长度的和的期望，对输入的质数 $p$ 取模。
**形式化题意：**
无限大的二维平面上刚开始有一个三条无向边构成的三角形，即存在点 $1,2,3$ 和边 $(1,2),(2,3),(3,1)$。接下来第 $i$ 秒：
- 等概率随机选择图形外圈（与无限远处在同一个块里）的一条无向边 $(u,v)$；
- 在该边外侧（无限远处所在的块）中建立点 $i+3$；
- 连接无向边 $(u,i+3)$ 和无向边 $(v,i+3)$；
输入 $n$，对于每个 $k\in[4,n]$ 求出 $k-3$ 秒后所有**无序点对**之间最短路的长度的和的期望值，对输入的质数 $p$ 取模。
输入格式
第一行两个整数 $n,p$。
输出格式
为避免输出量过大，输出一行一个整数表示 $k\in[4,n]$ 的所有答案的异或和。
说明/提示
**【样例 1 解释】**
此时共有三种情况：
不难发现每种情况下最短路总和都是 $1+1+1+1+1+2=7$，故期望为 $7$。
**【样例 2 解释】**
$k$ 从 $4$ 到 $10$ 的答案依次为：
```
7
13
800000027
800000038
190476238
138095302
124338708
```
**【数据范围】**
对于所有测试数据，$4\le n\le 10^6$，$1145143\le p\le 10^9+9$，保证 $p$ 是质数。
| 子任务编号 | $n$ | 分数 |
| :--------: | :-----: | :--: |
| $1$ | $=20$ | $5$ |
| $2$ | $=100$ | $10$ |
| $3$ | $=1000$ | $30$ |
| $4$ | $=10^6$ | $55$ |
**【提示】**
建议选手使用这份 std 使用的快速取模模板以减小常数因子：
```cpp
typedef __int128_t lll;
typedef unsigned long long ull;
struct FastMod{ull b, m;
inline void init(ull x){b = x, m = ((lll)1 > 64);
ull r = a - q * b;
return r >= b ? r - b : r;
}
}md;
```