东莞做营销型网站/cps推广接单平台

HDU - 4549

这道题以为是很水的矩阵快速幂，把矩阵{1，1，1，0}进行快速幂乘递推，ans[0][0]为a的指数，ans[0][1]为b的指数，但是疯狂wa，百度搜题解发现用到了费马小定理，A^X = A^( X mod phi(M) ) ( mod M )，又因为M为质数，所以phi(M) = M - 1，显然在矩阵乘法中%1000000006更不易溢出，所以推测wa结果为%1000000007是溢出所以错误了，以后进行幂乘运算时也算有一个优化，诶？好像发现了什么了不得的优化，这样以后矩阵乘法凡是模1e9+7的都变成%1e9+6就行了，厉害厉害

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
#define mod 1000000007
struct node
{long long m[2][2];
}ans;node mulp(node a, node b)
{node temp;memset(temp.m, 0, sizeof(temp.m));for(int i = 0; i < 2; i ++)for(int j = 0; j < 2; j ++){for(int k = 0; k < 2; k ++)temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j]) % (mod-1);}return temp;
}
void matrix_power(node a, long long b)
{ans.m[0][0] = ans.m[1][1] = 1;ans.m[0][1] = ans.m[1][0] = 0;while(b){if(b & 1) ans = mulp(ans, a);a = mulp(a, a);b >>= 1;}
}
long long quick_power(long long a, long long b)
{long long ans = 1;a%=mod;while(b){if(b&1) ans = (ans*a)%mod;a = (a*a)%mod;b >>= 1;}return ans;
}
int main()
{long long n, a, b;while(scanf("%lld%lld%lld",&a, &b, &n) != EOF){if(n == 0){printf("%lld\n",a%mod);continue;}node base = {1, 1, 1, 0};matrix_power(base, n - 1);printf("%lld\n",quick_power(a, ans.m[0][1]) * quick_power(b, ans.m[0][0]) % mod);}return 0;
}