Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef long long ll;
- typedef vector<vector<ll>> matrix;
- typedef vector<vector<double>> d_matrix;
- const int maxn = 1e5 + 10;
- const int INF = 2e9;
- const ll MOD = 100000007;
- class StairsToRazorTower
- {
- public:
- matrix multiply_two_matrices(matrix A, matrix B) {
- int n_a = (int) A.size(), m_a = (int) A[0].size();
- int n_b = (int) B.size(), m_b = (int) B[0].size();
- if(m_a != n_b) {
- return {{0}};
- }
- matrix res(n_a, vector<ll>(m_b, 0));
- for(int i = 0; i < n_a; i++) {
- for(int j = 0; j < m_b; j++) {
- ll c = 0;
- for(int k = 0; k < n_a; k++) {
- c += (A[i][k] * B[k][j]) % MOD;
- c %= MOD;
- }
- res[i][j] = c % MOD;
- }
- }
- return res;
- }
- ll nth_fibbonaci_number(ll x) {
- matrix A = {
- {1, 0, 1},
- {1, 0, 0},
- {0, 1, 0}
- };
- matrix B = A;
- // for(int i = 0; i < x; i++) {
- // A = multiply_two_matrices(A, B);
- // }
- matrix res = {
- {1, 0, 0,},
- {0, 1, 0},
- {0, 0, 1}
- };
- while(x) {
- if(x % 2 == 1) {
- res = multiply_two_matrices(res, A);
- }
- A = multiply_two_matrices(A, A);
- x /= 2;
- }
- return res[0][0];
- }
- ll getNumberOfWays( ll n )
- {
- return nth_fibbonaci_number(n);
- }
- };
- int main() {
- // nth_fibbonaci_number(8);
- // return 0;
- StairsToRazorTower s;
- for(int i = 1; i <= 10; i++) {
- cout << s.getNumberOfWays(969710026) << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement