Hack 一些 O(n) 做法和最优解

P4456 [CQOI2018] 交错序列

@[NaCly_Fish](/user/115864) @[PosVII](/user/271260) @[Walking_Dead](/user/124781)
by hxhhxh @ 2023-09-20 10:58:22


好闪,拜谢。
by DE_aemmprty @ 2023-09-20 11:06:18


@[hxhhxh](/user/429147) 这个确实是我处理不严谨的地方,对于 $n \geq p$ 的情况是很容易改的。对于 $a,b\geq p$ 首先可以将其对 $p-1$ 取模,主要问题在于需要计算出 $$[z^n]\frac{1+(1+x)z}{1-z-(1+x)z^2}$$ 的前 $a+b$ 项,没有逆元的话确实不好处理...
by NaCly_Fish @ 2023-09-20 11:28:47


更准确地说重点应该是要快速计算出 $$[z^n]\frac{1+(1+x)z}{1-z-(1+x)z^2}$$ 的 $x^p$ 和 $x^{p+1}$ 这两项系数
by NaCly_Fish @ 2023-09-20 11:34:02


好闪,拜谢。
by AFewSuns @ 2023-09-20 12:48:29


好闪,拜谢。
by HMZHMZHMZ @ 2023-09-20 13:00:14


|