글 읽기 - 피보나치 행렬 풀이

ekwoo 5년 전 0

피보나치 행렬로 짜봤는데 틀렸습니다가 나옵니다.

어디가 문제일까요?

#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> S;

vector<ll> matrix(vector<ll> A, vector<ll> B ){
	vector<ll> C;
	C.push_back((A[0]*B[0]+A[1]*B[2])), C.push_back((A[0]*B[1]+A[1]*B[3]));
	C.push_back((A[2]*B[0]+A[3]*B[2])), C.push_back((A[2]*B[1]+A[3]*B[3]));
	return C;
}

vector<ll> fibo(ll n){
	if(n==1) return S;
	vector<ll> x=fibo(n/2);
	x=matrix(x,x);
	return (n%2==1)?matrix(x,S):x;
}

int main(){
	ll n;
	scanf("%lld",&n);
	if(n==0) {printf("0\n"); return 0;}
	S.push_back(1), S.push_back(1);
	S.push_back(1), S.push_back(0);
	S=fibo(n);
	printf("%lld",S[1]);
}

jung2381187 5년 전 1

1만 번째 피보나치 수는 long long으로도 표현하지 못 할 만큼 큽니다.

ekwoo 5년 전 0

아하... 그렇군요

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

문제

문제

출처

ICPC

피보나치 행렬 풀이

ekwoo 5년 전 0

jung2381187 5년 전 1

ekwoo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말