P15463 [MX-X25-T7] "FeOI-5" Triangular Crystal.
Description
At the beginning, there is a triangle. Every second, a new point appears, and it connects with equal probability to two adjacent points on the current outermost boundary of the shape.
All points are labeled. All edges are undirected, and each edge has weight $1$.
Given $n$, for each $k \in [4, n]$, compute the expected value of the sum of shortest-path lengths between all pairs of points after the shape has grown to have exactly $k$ points, and take it modulo the given prime $p$.
**Formal statement:**
On an infinite 2D plane, initially there is a triangle made of three undirected edges, i.e. there are points $1, 2, 3$ and edges $(1,2), (2,3), (3,1)$. Then at the $i$-th second:
- Uniformly at random choose an undirected edge $(u, v)$ on the outer boundary of the shape (the boundary that is in the same face as infinity).
- Create a point $i+3$ on the outside of this edge (in the face containing infinity).
- Add undirected edges $(u, i+3)$ and $(v, i+3)$.
Given $n$, for each $k \in [4, n]$, compute the expected value of the sum of shortest-path lengths over all **unordered pairs of points** after $k-3$ seconds, and output it modulo the input prime $p$.
Input Format
The first line contains two integers $n, p$.
Output Format
To avoid an excessively large output, output one line with a single integer: the XOR of all answers for $k \in [4, n]$.
Explanation/Hint
**[Sample 1 Explanation]**
At this time, there are three possible cases:
It is easy to see that in each case the total sum of shortest paths is $1+1+1+1+1+2=7$, so the expectation is $7$.
**[Sample 2 Explanation]**
The answers for $k$ from $4$ to $10$ are:
```
7
13
800000027
800000038
190476238
138095302
124338708
```
**[Constraints]**
For all testdata, $4 \le n \le 10^6$, $1145143 \le p \le 10^9+9$, and it is guaranteed that $p$ is prime.
| Subtask ID | $n$ | Score |
| :--------: | :-----: | :---: |
| $1$ | $=20$ | $5$ |
| $2$ | $=100$ | $10$ |
| $3$ | $=1000$ | $30$ |
| $4$ | $=10^6$ | $55$ |
**[Hint]**
Contestants are advised to use the fast modulo template used in the std solution to reduce constant factors:
```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;
```
Translated by ChatGPT 5