来点组合意义

· · 题解

不妨取自然坐标系，初始时走的一步在十二向中随机，容易知道这转化不会影响答案。记 \mathrm X, \mathrm Y 分别为 x, y 方向坐标的随机变量。显然 \mathsf E\mathrm X = \mathsf E\mathrm Y = 0。

首先，由于两方向独立，要计算的就是 \mathsf E[\mathrm X^2 + \mathrm Y^2] = 2\mathsf E[\mathrm X^2] = 2\mathsf V\mathrm X。随后将 \mathrm X 拆解为 \sum \mathrm X_i，其中 \mathrm X_i 代表第 i 步的位移。这样

\mathsf V\mathrm X = \mathsf V\left[\sum_{i = 1}^n \mathrm X_i\right] = \sum_{i = 1}^n \mathsf V\mathrm X_i + \sum_{1\le i < j \le n} \mathrm{cov}(\mathrm X_i, \mathrm X_j)

其中 \mathsf E\mathrm X_i = 0，并仔细算一下知道 \mathsf V\mathrm X_i = \mathsf E[\mathrm X_i^2] = 1/2，而 \mathrm{cov}(\mathrm X_i, \mathrm X_j) = \mathsf E[(\mathrm X_i - 0)(\mathrm X_j - 0)] 只需要考虑总共 j-i 步中共有几次转动方向。取随机变量 \mathrm Z_{i - j} \sim B(j-i, p)，并由初始方向是均匀随机的，知道 \mathsf E[\mathrm X_i X_j] = \Re (e^{\mathrm i \frac{\pi}{6}})^{\mathrm Z_{i - j}} = \Re(1-p+pe^{\mathrm i \frac{\pi}{6}})^{i - j}，从而枚举 j-i 的长度 l，答案可以写为

&n + 2\sum_{l = 1}^n (n-l) \Re(1-p+pe^{\mathrm i \frac{\pi}{6}})^l \\ = \ &n + \sum_{l = 1}^n (n-l) \left[(1-p+pe^{\mathrm i \frac{\pi}{6}})^l + (1-p+pe^{-\mathrm i \frac{\pi}{6}})^l\right] \end{aligned}

进一步使用 mma 的化简繁而不难，故略去，总之能够做到 O(T\log n)。

代码很丑，就不放了，提交见此。