十二宫标志
NaCly_Fish
·
·
个人记录
算法 0：
猜测答案关于 n 是一个常系数线性递推数列，暴力算出前若干项后，使用 Berlekamp-Massey 之类的算法求解出递推式，即可以 \Theta(\log n) 的时间复杂度计算一组数据。
算法 1:
考虑枚举转向的次数 m，并枚举在 m+1 个方向上移动的步数 a_0,\cdots,a_m，其中 a_0 可以为 0，其它都必须是正整数。为了形式上简洁，这点不会在接下来的式子中写明。
看到「转向」这个操作，又是在平面上运动，那我们自然地想到用复数来刻画。设 \omega 为 12 阶 1 次单位根（即 \exp(\frac{\pi}{6}\text i)），则答案为
\sum_{m=0}^n p^m(1-p)^{n-m} \sum_{a_0+\cdots+a_m=n} \left| \sum_{j=0}^m a_j(\omega^j)\right|^2
而我们知道共轭复数的性质 |z|^2=z \bar z，所以内层和式可以表示为
\sum_{a_0+\cdots+a_m=n} \sum_{j=0}^m \sum_{k=0}^m a_j a_k \omega^j\omega^{-k}=\sum_{j=0}^m \sum_{k=0}^m \omega^{j-k}\sum_{a_0+\cdots+a_m=n}a_j a_k
再将 \sum a_ja_k 的值关于 j,k 做分类讨论：
-
j=k=0$ 时：$[x^n] \dfrac{x(1+x)}{(1-x)^3} \left( \dfrac{x}{1-x}\right)^m
-
j,k$ 中有一个为零，另一个不为零：$[x^n] \left( \dfrac{x}{(1-x)^2}\right)^2 \left( \dfrac{x}{1-x}\right)^{m-1}
-
j=k \neq 0$ 的情况有 $m$ 种：$[x^n] \dfrac{x(1+x)}{(1-x)^3} \left( \dfrac{x}{1-x}\right)^{m-1}\dfrac{1}{1-x}
-
j\neq k$，且均不为零的情况：$[x^n] \left(\dfrac{x}{(1-x)^2}\right)^2 \left( \dfrac{x}{1-x}\right)^{m-2}\dfrac{1}{1-x}
合并起来稍微化简一下，设
f_m= \sum_{j=1}^m \omega^j=\frac{\omega-\omega^{m+1}}{1-\omega}
答案就可以表示为
[x^n]\sum_{m = 0}^{\infty}p^m (1-p)^{n-m}\left( \frac{x}{1-x}\right)^m\frac{1}{(1-x)^3}\left( x(1+x)+x(f_m+\bar f_m)+mx + f_m \bar f_m\right)
等比数列求和可以得到一个关于 x 的有理分式，然后用你喜欢的线性递推算法提取其 [x^n] 系数即可。