题解：AT_fps_24_v 12 方向
Lynette_lovely
·
·
题解
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}
于是就可以快乐地卷积啦。