HDU3306 Another kind of Fibonacci(단순 매트릭스 신속 멱)

1861 단어 행렬 구조
아, 매트릭스 구조 방법을 배우고 싶었는데 갑자기 안 봐도 yy구조를 할 수 있다는 걸 알게 됐어요...
오른쪽에 뭐가 있는지 보세요.
제목 주소: 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; }

좋은 웹페이지 즐겨찾기