AT_fps_24_v 12 方向

· · 题解

摘自 https://www.luogu.com.cn/article/zgbd9hyb。

感觉官方题解写得很清晰啊，抄一下。

显然坐标不能只用整数表示，需要扩域到 \mathbb Q(\sqrt3) 上，于是不妨设当前坐标为 (\frac{a+\sqrt3b}2,\frac{c+\sqrt3d}2)，用 x^ay^bz^cs^d 表示。那么所求可以写成：

[x^{2H}y^0z^{2W}s^0]\left(x^2+x^{-2}+z^2+z^{-2}+(x+x^{-1})(s+s^{-1})+(y+y^{-1})(z+z^{-1})\right)^n

这东西同时出现了二次项和一次项，考虑用我们小学一年级就学过的方法全部转化为一次。设 X=x+x^{-1}，其余各项同理：

(X^2-2+Z^2-2+XS+YZ)^n=(X(X+S)+Z(Z+Y)-4)^n

这两部分独立，只需解决 [x^{2H}s^0](X(X+S))^k，即可轻松解决原问题。
令 x=pq,s=\frac pq，简单推下式子：

\begin{aligned} &[x^{2H}s^0]((x+x^{-1})(x+x^{-1}+s+s^{-1}))^k\\ =&[p^{2H}q^{2H}]((pq+(pq)^{-1})(pq+(pq)^{-1}+pq^{-1}+p^{-1}q))^k\\ =&[p^{2H}q^{2H}](pq+(pq)^{-1})^k(p+p^{-1})^k(q+q^{-1})^k\\ =&\sum_{i=0}^k\binom ki\binom k{H-i+k}^2 \end{aligned}

于是可以通过一次卷积求出 k=0\sim n 上述问题的答案。