• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

2周前 (04-07) 6次浏览

# 快速幂

``````struct Matrix{
static const int N=15;
ll a[N][N];
Matrix(ll e=0){
for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)a[i][j]=e*(i==j);
}
Matrix mul(Matrix A,Matrix B){
Matrix ans(0);
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
for (int k=1;k<=n;k++){
ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
}
}
}
return ans;
}
Matrix ksm(Matrix A,ll b){
Matrix ans(1);
while (b){
if (b&1)ans=mul(ans,A);
A=mul(A,A);b>>=1;
}
return ans;
}
}tmp;
``````

## 递推式的求解。

poj3070；

``````#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int t,n=2,k;
const int MOD = 10000;
struct Matrix{
static const int N=15;
ll a[N][N];
Matrix(ll e=0){
for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)a[i][j]=e*(i==j);
}
Matrix mul(Matrix A,Matrix B){
Matrix ans(0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
return ans;
}
Matrix ksm(Matrix A,ll b){
Matrix ans(1);
while (b){
if (b&1)ans=mul(ans,A);
A=mul(A,A);b>>=1;
}
return ans;
}
}tmp;
int main()
{
int q;
while (scanf("%d", &q) && q != -1)
{
tmp.a[1][1]=1,tmp.a[1][2]=1,tmp.a[2][1]=1,tmp.a[2][2]=0;
if(q==0)printf("0n");
else {
tmp=tmp.ksm(tmp,q-1);
printf("%lldn", tmp.a[1][1]);
}
}
return 0;
}
``````