글 읽기 - 피보나치 결과값은 잘나오는 것 같은데..

astrohsy 8년 전 0

20000까지 테스트해봤는데. 모두 맞는 결과가 나오는데...

소스제출하면 제출하자마자 틀렸습니다가 나오네요... 어디가 잘못된건지 모르겠어요

#include<iostream>
#include<vector>
using namespace std;

typedef vector<vector<long>>matrix;
const int K =2;

matrix mul(matrix A, matrix B)
{
    matrix C(K+1, vector<long>(K+1));
    for(int i = 1; i<=K; i++)
        for(int j =1; j<=K; j++)
            for(int k=1; k<=K; k++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % 1000000;
    
    return C;
}

matrix pow(matrix A, int p)
{
    if (p==1)
        return A;
    if (p % 2)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p/2);
    return mul(X, X);
}

int fib(int N)
{
    vector<long long> F1(K+1);
    F1[1] = 1;
    F1[2] = 1;
    
    matrix T(K+1, vector<long>(K+1));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = 1, T[2][2] = 1;
    
    if(N==1)
        return 1;
    T = pow(T, N-1);
    
    int res = 0;
    for(int i =1; i<=K; i++)
        res = (res + T[1][i] * F1[i]) % 1000000;
    
    return res;
}
int main()
{
    int n;
    cin>>n;
    
    if(n==0)
        cout<<0;
    else
        cout<<fib(n);
}

yukariko 8년 전 1

long은 32비트 환경에선 4바이트,

64비트 환경에선 8바이트로 처리되는데

이곳의 채점환경에 의해 4바이트로 동작하는것같네요.

long을 long long으로 바꿔보시기 바랍니다.

yukariko 8년 전 1

그리고 N의범위가 int형범위를 훨씬초과하는데 int로 선언하셨네요

astrohsy 8년 전 0

인풋범위를 생각을 못했네요.. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

피보나치 결과값은 잘나오는 것 같은데..

astrohsy 8년 전 0

yukariko 8년 전 1

yukariko 8년 전 1

astrohsy 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말