方法一：快速幂。但是肯定还是超时。
方法二：利用等比数列公式，但是有除法，做不下去了。
方法三：有点分治的味道..
n为偶数时，x^0+x^1+x^2+.......x^n=(x^0+x^1+x^2+.....x^(n/2))*(1+x^(n/2)）-x^(n/2);也就是F（n）=F(n/2)*(1+x^(n/2)）-x^(n/2);
n为奇数时，x^0+x^1+x^2+.......x^n=(x^0+x^1+x^2+.....x^(n/2))*(1+x^(n/2)）-x^(n/2)+x^n;也就是F（n）=F(n/2)*(1+x^(n/2)）-x^(n/2)+x^n;
用快速幂计算单个的，n的规模每次递归可以减半。。
仅仅是自己的想法，欢迎指出错误，或者提出更好的方法。
经过试验，减法也是满足同余的，也就是a%p-b%p+p)%p==(a-b)%p。
求x^0+x^1+x^2+.......x^n mod p； x，n，p<=10^9,布布扣,bubuko.com
求x^0+x^1+x^2+.......x^n mod p； x，n，p<=10^9
原文：http://www.cnblogs.com/vb4896/p/3887495.html