白駿11444、フィボナッチ数6
39096 ワード
質問する
https://www.acmicpc.net/problem/11444
に答える
この問題はできなかったので、解き方を見て...したがって、詳細な説明は省略する.
最初はn探索では絶対無理だと思っていたので、ログ探索でやってもいいと思いましたが、解決しにくいようで、数学関連の問題かもしれません.
この式を解く過程により,同じ形で現れることを試み,二乗分割征服を形成したが失敗した.
でも1時間考えたら諦めて正解を見た….これは行列乗算により得られた解である.
線形代数をよく勉強していないからだと思いますが...復習します
ミス
コード#コード#
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
using namespace std;
vector<vector<long long int>> ret_mat = { {1, 1}, {1, 0} }; // 재귀에서 반환할 행렬
vector<long long int> init = { 1, 1 };
vector<vector<long long int>> u = { {1, 1}, {1, 0} };
void DC(long long int n) {
if (n == 1) {
ret_mat[0][0] = u[0][0];
ret_mat[1][0] = u[1][0];
ret_mat[0][1] = u[0][1];
ret_mat[1][1] = u[1][1];
return;
}
else {
if (n % 2 == 1) {
DC((n - 1) / 2);
vector<vector<long long int>> temp = { {0, 0}, {0, 0} };
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * u[0][0] + temp[0][1] * u[1][0];
ret_mat[0][1] = temp[0][0] * u[0][1] + temp[0][1] * u[1][1];
ret_mat[1][0] = temp[1][0] * u[0][0] + temp[1][1] * u[1][0];
ret_mat[1][1] = temp[1][0] * u[0][1] + temp[1][1] * u[1][1];
ret_mat[0][0] = ret_mat[0][0] % 1000000007;
ret_mat[0][1] = ret_mat[0][1] % 1000000007;
ret_mat[1][0] = ret_mat[1][0] % 1000000007;
ret_mat[1][1] = ret_mat[1][1] % 1000000007;
}
else {
DC(n / 2);
vector<vector<long long int>> temp = { {0, 0}, {0, 0} };
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];
ret_mat[0][0] = ret_mat[0][0] % 1000000007;
ret_mat[0][1] = ret_mat[0][1] % 1000000007;
ret_mat[1][0] = ret_mat[1][0] % 1000000007;
ret_mat[1][1] = ret_mat[1][1] % 1000000007;
}
return;
}
}
int main() {
long long int n;
scanf("%lld", &n);
DC(n);
printf("%lld", ret_mat[1][0]);
return 0;
}
Reference
この問題について(白駿11444、フィボナッチ数6), 我々は、より多くの情報をここで見つけました https://velog.io/@sukha5364/백준-11444-피보나치-수-6テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol