题目链接

http://poj.org/problem?id=3070

刚刚学了矩阵，自己写了个Fibonacci ，这题看了一下输入输出，直接贴上代码，就AC了。矩阵真是个好方法。

代码

#include<stdio.h>
#include<string.h>
#define mod 10000

__int64 a[5];
__int64 b[3][3];

__int64 quick_mod(__int64 n)
{
__int64 i,j,k;
a[1]=1; a[2]=1;
b[1][1]=0; b[1][2]=1;
b[2][1]=1; b[2][2]=1;
while(n)
{
if(n&1)
{
__int64 s[3];
memset(s,0,sizeof(s));
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
s[i]=(s[i]+a[j]*b[j][i])%mod;
}
}
for(i=1;i<=2;i++)
a[i]=s[i];
n--;
}
n=n/2;
__int64 kk[5][5];
memset(kk,0,sizeof(kk));
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
for(k=1;k<=2;k++)
{
kk[i][j]=(kk[i][j]+b[i][k]*b[k][j])%mod;
}
}
}
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
b[i][j]=kk[i][j];
}
}
}
return a[1];
}

int main(void)
{
__int64 n;
while(scanf("%I64d",&n)==1)
{
if(n==-1)
return 0;
if(n==0)
{
printf("0\n");
continue;
}
printf("%I64d\n",quick_mod(n-1));
}
return 0;
}

用题目的方法也可以

代码

#include<stdio.h>
#include<string.h>
#define mod 10000

__int64 a[3][3],b[3][3];

__int64 quick_mod(__int64 n)
{
__int64 i,j,k;
__int64 kk[3][3];
a[1][1]=1; a[1][2]=1;
a[2][1]=1; a[2][2]=0;
b[1][1]=1; b[1][2]=1;
b[2][1]=1; b[2][2]=0;
while(n)
{
if(n&1)
{
memset(kk,0,sizeof(kk));
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
for(k=1;k<=2;k++)
{
kk[i][j]=(kk[i][j]+a[i][k]*b[k][j])%mod;
}
}
}
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
a[i][j]=kk[i][j];
}
}
n--;
}
n=n/2;
memset(kk,0,sizeof(kk));
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
for(k=1;k<=2;k++)
{
kk[i][j]=(kk[i][j]+b[i][k]*b[k][j])%mod;
}
}
}
for(i=1;i<=2;i++)
{
for(j=1;j<=2;j++)
{
b[i][j]=kk[i][j];
}
}
}
return a[1][2];
}

int main(void)
{
__int64 i,j,k,k1,k2,n;
while(scanf("%I64d",&n)==1)
{
if(n==-1) return 0;
if(n==0)
{
printf("0\n");
continue;
}
printf("%I64d\n",quick_mod(n-1));
}
return 0;
}

POJ-3070-Fibonacci