专栏文章

十二宫标志

NNaCly_Fish绒布球
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioebd81
此快照首次捕获于
2025/12/02 17:48
3 个月前
此快照最后确认于
2025/12/02 17:48
3 个月前
查看原文

算法 0：

猜测答案关于 nn 是一个常系数线性递推数列，暴力算出前若干项后，使用 Berlekamp-Massey 之类的算法求解出递推式，即可以 Θ(log⁡n)\Theta(\log n) 的时间复杂度计算一组数据。

算法 1:

考虑枚举转向的次数 mm，并枚举在 m+1m+1 个方向上移动的步数 a0,⋯ ,ama_0,\cdots,a_m，其中 a0a_0 可以为 00，其它都必须是正整数。为了形式上简洁，这点不会在接下来的式子中写明。
看到「转向」这个操作，又是在平面上运动，那我们自然地想到用复数来刻画。设 ω\omega 为 1212 阶 11 次单位根（即 exp⁡(π6i)\exp(\frac{\pi}{6}\text i)），则答案为
∑m=0npm(1−p)n−m∑a0+⋯+am=n∣∑j=0maj(ωj)∣2\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=zzˉ|z|^2=z \bar z，所以内层和式可以表示为
∑a0+⋯+am=n∑j=0m∑k=0majakωjω−k=∑j=0m∑k=0mωj−k∑a0+⋯+am=najak\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
再将 ∑ajak\sum a_ja_k 的值关于 j,kj,k 做分类讨论：
  • j=k=0j=k=0 时：[xn]x(1+x)(1−x)3(x1−x)m[x^n] \dfrac{x(1+x)}{(1-x)^3} \left( \dfrac{x}{1-x}\right)^m
  • j,kj,k 中有一个为零，另一个不为零：[xn](x(1−x)2)2(x1−x)m−1[x^n] \left( \dfrac{x}{(1-x)^2}\right)^2 \left( \dfrac{x}{1-x}\right)^{m-1}
  • j=k≠0j=k \neq 0 的情况有 mm 种：[xn]x(1+x)(1−x)3(x1−x)m−111−x[x^n] \dfrac{x(1+x)}{(1-x)^3} \left( \dfrac{x}{1-x}\right)^{m-1}\dfrac{1}{1-x}
  • j≠kj\neq k，且均不为零的情况：[xn](x(1−x)2)2(x1−x)m−211−x[x^n] \left(\dfrac{x}{(1-x)^2}\right)^2 \left( \dfrac{x}{1-x}\right)^{m-2}\dfrac{1}{1-x}
合并起来稍微化简一下，设
fm=∑j=1mωj=ω−ωm+11−ωf_m= \sum_{j=1}^m \omega^j=\frac{\omega-\omega^{m+1}}{1-\omega}
答案就可以表示为
[xn]∑m=0∞pm(1−p)n−m(x1−x)m1(1−x)3(x(1+x)+x(fm+fˉm)+mx+fmfˉm)[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)
等比数列求和可以得到一个关于 xx 的有理分式，然后用你喜欢的线性递推算法提取其 [xn][x^n] 系数即可。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...