sdut2605 A^X mod P 山东省第四届ACM省赛（打表，快速幂模思想，哈希）

本文出自：

题意：

f(x) = k, x = 1

f(x) = (a*f(x-1) + b)%m , x > 1

求出( a^(f(1)) + a^(f(2)) + a^(f(3)) + ...... + a^(f(n)) ) modular p.

1 <= n <= 10^6

0 <= a, k, a, b <= 10^9

1 <= m, p <= 10^9

本题目的关键在于大幂的分解和。。你要这样想，因为不停的求a的幂，所以肯定把算过的保存下来最合适。

打表。（- -）每次都是打表，shit。

把f分解为 fix * k + j 的形式，f就是f(x)的简称。(哈希）

然后关键是fix怎么整，多少合适。我觉得33333合适。为啥？

因为10^9 / 33333 =30000数组不大。然后余数也在33333之内，其好，那就它吧。

然后就用普通的幂模相乘打表就可以f[i] = (f[i-1] * a)mod p，这是个简单的例子，a和p没有实际含义。

这个题目我在做的时候蛋疼到二分法动态打表，但是超空间，因为不停的递归调用造成了超空间。。但是我觉得如果能够实现。。用栈的方法，应该会更加节省时间。因为用到的才计算。如果有不同的意见，请回复我，谢谢。

ac代码：