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代碼：