9도 OJ 1081: 밀어내기 수열(귀속, 이분법)

시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 6194
해결 방법: 864
제목 설명:
a0, a1, 그리고 an=p*a(n-1)+q*a(n-2)의 p,q를 지정합니다.여기 n>= 2.k개수 대 10000의 모형을 구하다.
입력:
입력은 5개의 정수를 포함합니다: a0, a1, p, q, k.
출력:
k번째 수 a(k)대 10000의 모형.
샘플 입력:

20 1 1 14 5

샘플 출력:

8359

출처:
2009년 청화대학 컴퓨터 연구 생기시험 진제
생각:
한 걸음 한 걸음 밀어붙이는 것은 틀림없이 시간을 초과해야 한다.이런 n번째 수를 구하는 추출 문제에 대해logn의 해법이 있다.
기본 사상은 a(n)가 a(n/2)에서 얻고 차례차례 순환하는 것이다.
an=p*a(n-1)+q*a(n-2)
an=p2*a(n-2)+q2*a(n-4)
그중 p2=(p*p+2*q), q2=-q*q
이런 사상은 전형적인 이분법으로 이 문제의 중점은 일종의 문제풀이 사상을 배운 것이다.
코드:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int main(void)
{
    int p, q, p2, q2, k;
    long long a0, a1, a2, a3;
 
    while (scanf("%lld%lld%d%d%d", &a0, &a1, &p, &q, &k) != EOF)
    {
        if (k == 0)
        {
            printf("%lld
", a0);
            continue;
        }
        a0 %= 10000;
        a1 %= 10000;
        p %= 10000;
        q %= 10000;
        while (k>1)
        {
            a2 = p*a1+q*a0;
            while (a2<0)
                a2 += 1000000000;
            a2 %= 10000;
            if (k%2 == 1)
            {
                a3 = p*a2+q*a1;
                while (a3<0)
                    a3 += 1000000000;
                a3 %= 10000;
                a0 = a1;
                a1 = a3;
            }
            else
                a1 = a2;
            p2 = (p*p+2*q)%10000;
            q2 = -q*q;
            while (q2<0)
                q2 += 1000000000;
            q2 %= 10000;
            p = p2;
            q = q2;
            k /= 2;
        }
        printf("%lld
", a1);
    }
 
    return 0;
}
/**************************************************************
    Problem: 1081
    User: liangrx06
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:912 kb
****************************************************************/

다른 사람의 코드는 다른 귀속 방식을 사용했는데 사상은 유사하다.

#include<stdio.h>
#define MOD 10000
long long a0,a1,p,q,k;
void matrixpow(long long *data,long long k)
{
        long long t1,t2,t3,t4;        
        long long d1,d2,d3,d4;
        d1 = p;
        d2 = q;
        d3 = 1;
        d4 = 0;
        if(k == 1 || k == 0)
                return;        
        matrixpow(data,k/2);
        t1 = (data[0]*data[0]+data[1]*data[2])%MOD;
        t2 = (data[0]*data[1]+data[1]*data[3])%MOD;
        t3 = (data[0]*data[2]+data[2]*data[3])%MOD;
        t4 = (data[1]*data[2]+data[3]*data[3])%MOD;
        data[0] = t1;
        data[1] = t2;
        data[2] = t3;
        data[3] = t4;
        if(k&1)
        {
                t1 = (data[0]*d1+data[1]*d3)%MOD;
                t2 = (data[0]*d2+data[1]*d4)%MOD;
                t3 = (data[2]*d1+data[3]*d3)%MOD;
                t4 = (data[2]*d2+data[3]*d4)%MOD;
                data[0] = t1;
                data[1] = t2;
                data[2] = t3;
                data[3] = t4;
        }
}
void main()
{        
        long long data[4];
        long long res;
        while(scanf("%lld%lld%lld%lld%lld",&a0,&a1,&p,&q,&k)!=EOF)
        {
                data[0] = p;
                data[1] = q;
                data[2] = 1;
                data[3] = 0;
                matrixpow(data,k-2);
                if(k == 0)
                        res = a0%MOD;
                else
                {
                        if(k == 1)
                                res = a1%MOD;
                        else
                        {
                                if(k>2)
                                        res = (data[0]*p*a1+a1*q*data[2]+a0*p*data[1]+a0*q*data[3])%MOD;
                                else
                                        res = (a1*p+a0*q)%MOD;
                        }
                }
                printf("%lld
",res);
        }
}