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;
}
转载于:https://www.cnblogs.com/RootVount/p/11559755.html
相关资源：JAVA上百实例源码以及开源项目
