白駿11444、フィボナッチ数6


質問する


https://www.acmicpc.net/problem/11444

に答える


この問題はできなかったので、解き方を見て...したがって、詳細な説明は省略する.
最初はn探索では絶対無理だと思っていたので、ログ探索でやってもいいと思いましたが、解決しにくいようで、数学関連の問題かもしれません.

この式を解く過程により,同じ形で現れることを試み,二乗分割征服を形成したが失敗した.
でも1時間考えたら諦めて正解を見た….これは行列乗算により得られた解である.
線形代数をよく勉強していないからだと思いますが...復習します

ミス

  • の実施において、試験画像ret=retのように直ちに値が使用されるが、論理的に不明であるため値が歪む、最終的にtempが作成され(時間の無駄)
  • が解決する.
  • 行列乗算は長い間実施されている
  • コード#コード#

    #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;
    
    }