AT_fps_24_v 12 方向

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

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

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

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

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

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