V - 12 Directions

考虑

x, y, z, w

分别表示向量

(\frac 1 2, 0), (0, \frac 1 2), (\frac {\sqrt 3} 2, 0), (0, \frac {\sqrt 3} 2)

，则一次操作的生成函数为：

\left(x^2 + \frac 1 {x^2} \right) + \left(y^2 + \frac 1 {y^2} \right) + \left(x + \frac 1 x \right) \left(w + \frac 1 w \right) + \left(y + \frac 1 y \right) \left(z + \frac 1 z \right)

考虑

\left(x + \frac 1 x \right)^2 = x^2 + \frac 1 {x^2} + 2

则可化为

\left(x + \frac 1 x \right) \left(x + \frac 1 x + w + \frac 1 w \right) + \left(y + \frac 1 y \right) \left(y + \frac 1 y + z + \frac 1 z \right) - 4

此时将三部分二项式展开，于是只需要对

n \in [0, N]

分别计算

[x^{2H} y^0] \left(x + \frac 1 x \right)^n \left(x + \frac 1 x + y + \frac 1 y \right)^n

即可。

然而此时并不太好直接展开化简，考虑将右边部分因式分解。

考虑

\left(p + \frac 1 p \right) \left(q + \frac 1 q \right) = pq + \frac 1 {pq} + \frac p q + \frac q p

于是令

\begin{cases} pq &= x \\ \frac p q &= y \end{cases}

即

\begin{cases} p &= \sqrt {xy} \\ q &= \sqrt {\frac x y} \end{cases}

设

p, q

需要提前的系数为

r, s

有

\begin{cases} \frac 1 2 (r + s) &= 2H \\ \frac 1 2 (r - s) &= 0 \\ \end{cases}

解得

\begin{cases} r &= 2H \\ s &= 2H \\ \end{cases}

则所求即

\begin{aligned} & [p^{2H} q^{2H}] \left(pq + \frac 1 {pq}\right)^n \left(p + \frac 1 p\right)^n \left(q + \frac 1 q\right)^n \\ =& \sum_{i = 0} \binom n i \binom n {n + H - i} ^ 2 \\ =& \sum_{i = 0} \frac {(n!)^3} {(n - i)! i! [(i - H)!]^2 [(n + H - i)!]^2} \end{aligned}

于是就可以快乐地卷积啦。

题解：AT_fps_24_v 12 方向