글 읽기 - 2086 문제 틀린 이유

kcl5363 6년 전 0

거듭제곱 알고리즘 응용해서 피보나치 수열을 행렬로 바꿔 풀어 보았습니다.

시간복잡도에서 많은 줄어든 거에 반에 틀렸다고 판정합니다. 오버플로우 발생 부분도 잘 안보이네요.... 8%에서 틀림판정 받은거 보니 오버플로우 같은데..

어느 부분이 잘못 됬는 지 짚어 주실 분 있나요???????? ㅠㅠㅠ

#include <iostream>
using namespace std;

typedef struct matrix{
	unsigned long long int mat[2][2];
}Matrix;

Matrix I = {1,1,1,0};

Matrix Power_Matrix(unsigned long long int a){
	if(a==1)return I;
	Matrix tmp;
	Matrix m;
	Matrix m1;
	
	if(a%2==0){
		tmp=Power_Matrix(a/2);
		m.mat[0][0]=((tmp.mat[0][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((tmp.mat[0][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((tmp.mat[1][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((tmp.mat[1][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][1]%1000000000))%1000000000;
	}
	else{
		tmp=Power_Matrix((a-1)/2);
		m.mat[0][0]=((tmp.mat[0][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((tmp.mat[0][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((tmp.mat[1][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((tmp.mat[1][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][1]%1000000000))%1000000000;	
		m1=m;
		m.mat[0][0]=((m1.mat[0][0]*I.mat[0][0]%1000000000)+(m1.mat[0][1]*I.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((m1.mat[0][0]*I.mat[0][1]%1000000000)+(m1.mat[0][1]*I.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((m1.mat[1][0]*I.mat[0][0]%1000000000)+(m1.mat[1][1]*I.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((m1.mat[1][0]*I.mat[0][1]%1000000000)+(m1.mat[1][1]*I.mat[1][1]%1000000000))%1000000000;
	}
	return m;
}

int main (){
	unsigned long long int a,b;
	Matrix M1,M2;
	cin>>a>>b;
	M1=Power_Matrix(a+1);
	M2=Power_Matrix(b+2);
	cout<<M2.mat[0][1]-M1.mat[0][1]<<endl;
	return 0;
}

bupjae 6년 전 5

다음 입력 데이터로 테스트해 보세요

나머지로 나올 수 없는 수가 나오고 있습니다

1001 1003

kcl5363 6년 전 0

마지막에 뺄 때 음수가 나와서 그렇게 되었네요 감사합니다 해결했어요~~~~~~~^^

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

문제

문제

출처

ICPC

2086 문제 틀린 이유

kcl5363 6년 전 0

bupjae 6년 전 5

kcl5363 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말