long long pow(int base,int n)
{
if (n == 0)
return 1;
if (n == 1)
return base;
long long ans = pow(base,n/2);
ans *= ans;
if (n % 2 == 1)
ans *= base;
return ans;
}
快速幂
就是把写法写成非递归的,可以用位运算,其实不用也没关系,可能是写起来比较好看吧。
举个例子,相当于
long long int fun( int a, int b )
{
long long int r = 1;
int base = a;
while ( b != 0 )
{
if(b & 1)
{
r *= base;
}
base *= base;
b >>= 1;
}
return r;
}
快速乘
long long fastMultiplication(long long a,long long b)
{
long long ans = 0;
while(b)
{
if(b % 2 == 1)
{
b--;
ans = ans + a;
ans %= mod;
}
else
{
b /= 2;
a = a + a;
a %= mod;
}
}
return ans;
}
矩阵快速幂
就是把乘法换成矩阵的乘法。
最简单就是用在 Fibonacci 中了。
struct Matrix
{
int edges[MAXN][MAXN];
Matrix() {}
Matrix operator*(Matrix const &b)const
{
Matrix res;
memset(res.edges, 0, sizeof(res));
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
for (int k = 0; k < MAXN; k++)
res.edges[i][j] = (res.edges[i][j] + this->edges[i][k] * b.edges[k][j]) % MOD;
return res;
}
};
Matrix fastpow(Matrix base, int n)
{
Matrix res;
memset(res.edges, 0, sizeof(res.edges));
for (int i = 0; i < MAXN; i++)
res.edges[i][i] = 1;
while (n > 0)
{
if (n & 1) res = res * base;
base = base * base;
n >>= 1;
}
return res;
}