公式很容易想出来 an = 2^( n - 1 ) + 1
然后要用到快速幂取模 在logn的时间内算出 幂
AC代码如下:
#include
#include
#include
#include
using namespace std;
long long DFS( long long base, long long exp, long long mod ){//...
1.快速幂取模
http://www.cnblogs.com/yinger/archive/2011/06/08/2075043.html
快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c
long exp_mod(long a,long n,long b)
{
long t;
...