hdu 4549 M斐波那契数列（矩阵高速幂，高速幂降幂）

http://acm.hdu.edu.cn/showproblem.php?pid=4549

f[0] = a^1*b^0%p，f[1] = a^0*b^1%p，f[2] = a^1*b^1%p…..f[n] = a^fib[n-1] * b^fib[n-2]%p。

这里p是质数，且a,p互素，那么我们求a^b%p，当b非常大时要对b降幂。

由于a,p互素，那么由费马小定理知a^(p-1)%p = 1。令b = k*(p-1) + b’。a^b%p = a^(k*(p-1)+b’)%p = a^(k*(p-1))%p * a^b’%p

= a^b’%p。

当中p’ = b%(p-1)。

那么上题的fib[n-1]和fib[n-2]能够经过矩阵高速幂对(p-1)取模，实现降幂以后再用高速幂求得。

事实上a^b%c较一般的形式是a^(b%phi[c]+phi[c])%c (b>=phi[c])，在c是素数或a与c互素的时候能够简化为a^(b%(c-1))%c。

纳闷了一中午，结果把fib数列弄错了。f[0] = 0, f[1] = 1,f[n] = f[n-1]+f[n-2]（n >= 2）。第0项是0，sad….

http://www.narutoacm.com/archives/a-pow-b-mod-m/

对大神表示深深的ym.

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 110;
const int mod = 1000000007;struct matrix
{
LL mat[3][3];
void init()
{
memset(mat,0,sizeof(mat));
for(int i = 0; i < 2; i++)
mat[i][i] = 1;
}
}m;LL a,b,n;matrix mul_matrix(matrix x, matrix y)
{
matrix ans;
memset(ans.mat,0,sizeof(ans.mat));
for(int i = 0; i < 2; i++)
{
for(int k = 0; k < 2; k++)
{
if(x.mat[i][k] == 0) continue;
for(int j = 0; j < 2; j++)
ans.mat[i][j] = (ans.mat[i][j] + x.mat[i][k]*y.mat[k][j])%(mod-1);
}
}
return ans;
}matrix pow_matrix(matrix m, LL n)
{
matrix ans;
ans.init();
while(n)
{
if(n&1)
ans = mul_matrix(ans,m);
m = mul_matrix(m,m);
n >>= 1;
}
return ans;
}LL pow_mod(LL a, LL b)
{
LL res = 1;
a = a%mod;
while(b)
{
if(b&1)
res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res;
}int main()
{while(~scanf("%lld %lld %lld",&a,&b,&n))
{
m.mat[0][0] = m.mat[0][1] = m.mat[1][0] = 1;
m.mat[1][1] = 0;
if(n == 0)
{
printf("%lld\n",a%mod);
continue;
}
if(n == 1)
{
printf("%lld\n",b%mod);
continue;
}
else if(n == 2)
{
printf("%lld\n",a*b%mod);
continue;
}
matrix ans = pow_matrix(m,n);
LL res = pow_mod(a,ans.mat[1][1]) * pow_mod(b,ans.mat[0][1]) %mod;
printf("%lld\n",res);
}
return 0;
}