ABC293E 题解
__vector__
·
·
题解
说一个很简单的分治做法。
先把式子写下来：
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 提交记录