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;
}
知识兔