피보나치3 codeforces #597 div2 C - Constanze's Machine ( 피보나치 , 구현) https://codeforces.com/contest/1245/problem/C 단어를 입력하면 m은 nn으로, w는 uu로 바꿔서 출력하는 기계가 있다. (출력에 m이나, w가 나올 수 없다. 이경우 0 출력) 예를들어 단어에 nnn이라는 문자배열이 있다면, 가능한 입력은 nnn mn nm 총 세가지가 존재한다. 'n'이 k번 연속한 문자배열을 만들 수 있는 입력은 피보나치 수열을 이루게 된다. (왜 그런지는 모르겠다. 몇번 해보니까 규칙이 보임) 따라서 단어에서 n이 나오는 idx를 기록한 idx_n과 u가 나오는 idx를 기록한 idx_u에 대해서 적절히 연산해 주었다. #include #include #include using namespace std; const int MAX = 1e5+1; .. 2019. 11. 3. BOJ 11444 - 피보나치 수 6 (행렬곱, 점화식 이용) https://www.acmicpc.net/problem/11444 MOD가 10의 거듭제곱꼴이 아니므로 피사노 주기를 사용할수 없다. 따라서 행렬곱을 이용해야 한다. https://www.acmicpc.net/blog/view/28 설명은 이곳 참고 #include #include using namespace std; typedef long long ll; typedef vector matrix; const ll MOD = 1000000007LL; matrix operator * (const matrix& a, const matrix& b) { int n = a.size(); matrix c(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j.. 2019. 9. 27. BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) https://www.acmicpc.net/problem/2749 피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함) 그중 특히 MOD = 10^k (k>2) 인 경우 PRD = 15*10^(k-1)이다. fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다. 피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다. #include #include using namespace std; typedef long long ll; const int MOD = 1e6; const int PRD = 15e5; ll dp[PRD]; ll fibo(int k) { if (k > n; fill(dp, dp + PRD, -1); cout 2019. 9. 27. 이전 1 다음