문제 URL : https://www.acmicpc.net/problem/11444
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
문제 접근법 :
피보나치 행렬을 이용하는 문제인데
피보나치 행렬이 있다는것을 알았지만 어떻게 유도해내는지 몰라서 공부해봤습니다. 그것만 유도하면
해당 수의 n승을 구하면되기때문에
유도 방법을 알려드리겠습니다.
일반적으로
피보나치 공식은
이건 너무쉽고 당연하듯이 여러분도 알고있는공식입니다.
이식을 좀 바꿔보죠
자이렇게 근데 fi=fi 이건 당연한겁니다 그치만 뒤에다 0을 추가해줍니다. 0을 더해도 어차피 그대로니 상관없겠죠?
자그럼 인제 이식들을 연립방정식이라 생각하고 행렬로 바꿔보죠
이렇게 바뀝니다. 자그럼 식을 간단하게 바꿔보죠
이렇게 바꿔보죠 그럼 생각해보시면 (Fi+1 Fi)는 A(Fi-1 Fi-2) 였을거라 생각할수있습니다.
이렇게 쉽게 추측할수있죠 그렇다면 실제론
이와같은 식이 성립하겠죠 그렇다면 반복한다면
이와같은식이되고 i가 A행렬은 i개 존재하고 F1=1 이었고 F0은 0이었으니 따라서 최종적으로
.
와같은 식이 나옵니다
이걸이용해서 코드를 짜시면 됩니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<vector<ll>>
ll mod = 1000000007;
ll n;
vll operator*(vll &x,vll &y) {
vll z(2, vector<ll>(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
z[i][j] += x[i][k] * y[k][j];
}
z[i][j] %= mod;
}
}
return z;
}
void input() {
cin >> n;
}
void solve() {
vll x = { {1,1},{1,0} };
vll res = { {1,0},{0,1} };
while (n) {
if (n % 2)
res = x * res;
x = x * x;
n /= 2;
}
cout << res[1][0] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 5525 IOIOI (0) | 2022.11.01 |
|---|---|
| 백준 1007 벡터 매칭 (1) | 2022.11.01 |
| 백준 15730 수영장 사장님 (1) | 2022.08.04 |
| 백준 14554 The Other Way (0) | 2022.08.04 |
| 백준 13911 집 구하기 (0) | 2022.07.31 |
