本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-03-12 17:56:36

说一个很简单的分治做法。
先把式子写下来：
$A^0 + A^1 + A^2 + A^3 + \cdots + A^{X-1}$
如果将式子的前 $\lfloor \frac{X}{2} \rfloor$ 项与后面的项分开，可以发现，前半部分计算出来后可以快速计算得到后半部分。

设前半部分 $res_1 = A^0 + A^1 + A^2 + \cdots + A^{\lfloor \frac{x}{2} \rfloor -1}$。

假设 $X$ 是偶数，那么后半部分即 $A^{\lfloor \frac{X}{2}\rfloor} + \cdots + A^{X-1} = A^{\lfloor \frac{X}{2}\rfloor} \cdot res_1$。

若 $X$ 是奇数，那就先按 $X$ 是偶数的式子计算，最后在原来的答案的基础上加上 $A^{X-1}$ 即可。

现在就找出了已知前半部分，$O(1)$ 得知后半部分的方法。

分治即可。

Atcoder 提交记录