Vagaa II 라 는 이상 한 개 (행렬 상승)

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1100
매트릭스 곱셈

A Strange Dog called Vagaa II
Time Limit: 1000 MS
Memory Limit: 65536 K

Total Submit: 105(32 users)
Total Accepted: 29(23 users)
Special Judge: No

Description
Leyni has a strange dog called Vagaa and it is just born.(We call it 0 years old.) 1.Vagaa will lay a small dog each year till it is 2 years old.(It will lay when it's 2 years old and won't lay when it's 3 years old.)2.Vagaa will live forever.(Because it believes in ChunGe.)3.The same as its child.(Its child will lay and live as the same as Vagaa.) For example,0 year : 1 dog. (Vagaa(0 years old).)1 year : 2 dog. (Vagaa(1 years old) and its child(0 years old).)2 year : 4 dog. (Vagaa(2) and its child(1) will lay 2 dogs(0).)3 year : 7 dog. (Vagaa(3) won't lay. Its child(2) will lay 1 dog(0). The other 2 dogs(1) will lay 2 dogs(0).)4 year : 12 dog. (...) Now, Leyni want to know how many dogs he has in total when Vagaa is N years old.
Input
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. Then T test cases follow.For each test case:Line 1. An Integer N.(0≤N≤109)
Output
For each test case:Line 1. Output the number of dogs Leyni has in total MOD 10007.
Sample Input
501234
Sample Output
124712
Author
하 이 공 2011 봄 학교 경기

이 문제 의 전달 공식 은 바로 a [n] = a [n - 1] + a [n - 2] + 1 이다.
피 보 나치 수열 과 유사 하 다.
하지만 수치 가 10 ^ 9 개 는 저장 할 수 없습니다.
그래서 행렬 의 상승 편 의 를 이용 했다.

전달 공식 을 실현 하 다.
코드:
#include
#include

int m=10007;

int A[1][3];
int B[3][3]={0,1,0,1,1,0,0,1,1};
int C[3][3];

void mul(int a[][3],int b[][3],int c[][3])
{/ / 기능, a * b 존재 c 리 구하 기
    int i,j,h;
    for(i=0;i<3;i++)
     for(j=0;j<3;j++)
    {
       c[i][j]=0;
       for(h=0;h<3;h++)
         c[i][j]+=a[i][h]*b[h][j];
       c[i][j]%=m;
    }
}

void qiu (int x, int a [] [3]) / / B 의 x 제곱 을 구하 여 a 리 에 존재 합 니 다.
{
    int i,j;
    int b[3][3];
    if(x==1)             //x 가 1 일 때 B 를 a 리 에 직접 저장 합 니 다.
    {
        for(i=0;i<3;i++)
         for(j=0;j<3;j++)
           a[i][j]=B[i][j];
        return;
    }
    if(x%2==0)
    {
        qiu(x/2,b);
        mul(b,b,a);
    }
    else
    {
        qiu(x-1,b);
        mul(b,B,a);
    }
}

int main()
{
    int c[3][3];
    int i,j,h,l,p,n,N;
    while(scanf("%d",&N) != EOF)
    while(N--)
    {
       scanf("%d",&p);
       //if(p==0) printf("1");
       //else if(p==1) printf("2");
       //else if(p==2) printf("4");
      // else if(p==3) printf("7");
      // else
      // {
          A[0][0]=0;A[0][1]=1;A[0][2]=1;
          qiu(p+1, C);
          /*for(i=0; i<1; i++)
            for(j=0; j<3; j++)
            {
               c[i][j] = 0;
               for(h=0; h<3; h++)
               c[i][j] += A[i][h] * C[h][j];
               c[i][j] %= m;
            }*/
          mul(A,C,c);
          n = c[0][0] % m;
          printf("%d", n);
      // }
    }
    return 0;
}

작은 민감 한 코드 를 추가 합 니 다:

#include <stdio.h>
#include <cstring>
using namespace std;

int A[3][3] = {0, 0, -1, 1, 0, 0, 0, 1, 2};
int B[3][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1};
int C[3][3];

void mul(int a[3][3], int b[3][3], int c[3][3])
{
    int i, j, k;
    int f[3][3];

    for(i = 0; i < 3; ++i)
    for(j = 0; j < 3; ++j)
    {
        f[i][j] = 0;
        for(k = 0; k < 3; ++k)
            f[i][j] += a[i][k] * b[k][j];
        //f[i][j] %= 10007;
        if(f[i][j]>0) f[i][j]%=10007;
        while(f[i][j]<0)f[i][j]+=10007;
    }
    for(i = 0; i < 3; ++i)
    for(j = 0; j < 3; ++j)
    c[i][j] = f[i][j];
}

void f(int arr[3][3], int n)
{
    int a[3][3];
    int i, j, k;
    if(n == 0) return;
    else if(n == 1)
    {
        for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
        C[i][j] = arr[i][j];
    }
    else if(n == 2)
    {
        mul(arr, arr, C);
        return;
    }
    else
    {
        f(arr, n / 2);
        for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
        a[i][j] = C[i][j];
        mul(a, a, C);
        if(n&1)
        mul(arr, C, C);
        /*if(n%2==0)
        {
            f(arr,n/2);
            for(i = 0; i < 3; ++i)
           for(j = 0; j < 3; ++j)
          a[i][j] = C[i][j];
          mul(a, a, C);
        } 
        else
        {
            f(arr,n-1);
            for(i = 0; i < 3; ++i)
           for(j = 0; j < 3; ++j)
          a[i][j] = C[i][j];
          mul(a,arr,C);
        }   */    
    }
}


int main()
{
    int t, n;
    int m;
    int sum;
    int i, j, k;
    int a[3] = {1, 2, 4};
    int arr[3];
    while(scanf("%d", &t) != EOF)
    {
        while(t--)
        {
            scanf("%d", &n);
            if(n == 0)
                printf("1
");
            else if(n == 1)
                printf("2
");
            else if(n == 2)
                printf("4
");
            else
            {
                f(A, n );
  /*              for(i = 0; i < 3; ++i)
                {
                    for(j = 0; j < 3; ++j)
                    printf("%d ", C[i][j]);
                    printf("
");
                }
  */
                memset(arr, 0, sizeof(arr));
                for(j = 0; j < 3; j++)
                for(k = 0; k < 3; k++)
                {
                    arr[j] += a[k] * C[k][j];
                    arr[j] %= 10007;
                }
                arr[0] %= 10007;
                printf("%d
", arr[0]);
            }
        }
    }
    return 0;
}

이 공식 은 a [n] = 2 * a [n - 1] - a [n - 3];
사실 똑 같 아 요.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

JScall () 및 apply () 방법에 대한 인스턴스 요약 사용

최근에 JacvaScript에서의call()방법과apply()방법을 만났습니다. 그리고 어떤 때는 이 두 방법이 정말 중요합니다. 그러면 이 두 방법의 사용과 차이를 정리하겠습니다. 모든 함수는 두 가지 비계승적인 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Vagaa II 라 는 이상 한 개 (행렬 상승)

좋은 웹페이지 즐겨찾기