HDU3306 Another kind of Fibonacci(단순 매트릭스 신속 멱)
1861 단어 행렬 구조
오른쪽에 뭐가 있는지 보세요.
제목 주소: Another kind of Fibonacci
AC 코드:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int mod=10007;
int p[4][4],a[4][4],tmp[4][4];
int n,x,y,ans[4],res[4];
void init()
{
int i,j;
a[0][0]=1,a[0][1]=x*x%mod,a[0][2]=y*y%mod,a[0][3]=2*x*y%mod;
a[1][0]=0,a[1][1]=x*x%mod,a[1][2]=y*y%mod,a[1][3]=2*x*y%mod;
a[2][0]=0,a[2][1]=1,a[2][2]=0,a[2][3]=0;
a[3][0]=0,a[3][1]=x,a[3][2]=0,a[3][3]=y;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
p[i][j]=a[i][j];
}
void cal1()
{
int i,j,k;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
tmp[i][j]=a[i][j];
a[i][j]=0;
}
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
a[i][j]=(a[i][j]+tmp[i][k]*p[k][j])%mod;
}
void cal2()
{
int i,j,k;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
tmp[i][j]=p[i][j];
p[i][j]=0;
}
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
p[i][j]=(p[i][j]+tmp[i][k]*tmp[k][j])%mod;
}
int main()
{
int i,j;
while(cin>>n>>x>>y)
{
x%=mod,y%=mod;
ans[0]=2;
ans[1]=ans[2]=ans[3]=1;
init();
n-=2;
while(n)
{
if(n&1)
cal1();
cal2();
n>>=1;
}
memset(res,0,sizeof(res));
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
res[i]=(res[i]+a[i][j]*ans[j])%mod;
}
}
printf("%d
",res[0]);
}
return 0;
}