Description
WZ是个蛋痛的人,总是喜欢琢磨蛋痛的事,比如他最近想知道上楼梯总共有多少种方式。已知他一步可以迈一阶、两阶或者三阶,现在给你楼梯的阶数,让你计算总共有多少种方式。
Input
输入有多组数据,每组数据占一行,表示楼梯的阶数。(1<=N<=100,000,000,000)
Output
对于每组数据,输出一行,表示上楼方式的总数 % 1000000007。
Sample Input
1 2
Sample Output
1 2
Source
Unknown
#include<bits/stdc++.h> using namespace std; #define ll long long const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int maxn = 1000 + 8; ll n; struct matrix { ll m[3][3]; }b, tp, res, init; matrix mul(matrix a, matrix b) { matrix c; for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { c.m[i][j] = 0; for(int k = 0; k < 3; k++) { c.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod; c.m[i][j] %= mod; } } } return c; } matrix matrix_mi(matrix p, ll k) { matrix t = res; while(k) { if(k & 1) t = mul(t, p); k >>= 1; p = mul(p, p); } return t; } int main() { // std::ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) init.m[i][j] = 0; for(int i = 0; i < 3; i++) init.m[0][i] = 1; init.m[1][0] = 1; init.m[2][1] = 1; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) if(i == j) res.m[i][j] = 1; else res.m[i][j] = 0; while(cin >> n) { b = init; if(n == 1) cout << "1" << '\n'; else if(n == 2) cout << "2" << '\n'; else if(n == 3) cout << "4" << '\n'; else { tp = matrix_mi(b, n - 3); cout << ((4 * tp.m[0][0]) % mod + (2 * tp.m[0][1]) % mod + tp.m[0][2] % mod) % mod << '\n'; } } return 0; }