Description WZ是个蛋痛的人，总是喜欢琢磨蛋痛的事，比如他最近想知道上楼梯总共有多少种方式。已知他一步可以迈一阶、两阶或者三阶，现在给你楼梯的阶数，让你计算总共有多少种方式。 Input 输入有多组数据，每组数据占一行，表示楼梯的阶数。(1<=N<=100,000,000,000) Output 对于每组数据，输出一行，表示上楼方式的总数 % 1000000007。 Sample Input
1 2
Sample Output
1 2
首先：递推公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];由于这里数据太大，所以用 了矩阵快速幂，，， 参考师哥博客： SDNU1085.爬楼梯再加强版（矩阵快速幂+矩阵关系推导） 虽然感觉把图很丑，但是，还是可以 简单理解的。。
#include<stdio.h> #include<iostream> #include<map> #include<algorithm> #include<cstring> #include<string.h> #include<math.h> #include<vector> #include<map> using namespace std; typedef long long ll; #define MAXN 10005 #define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int #define MOD 1000000007 struct node{ ll m[3][3]; }stu; node mul(node a, node b) { node tem; memset(tem.m, 0, sizeof(tem.m)); for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) tem.m[i][j] = (tem.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD; return tem; } node qaq(node ans, ll b) { memset(stu.m, 0, sizeof(stu.m)); stu.m[0][0] = stu.m[1][1] = stu.m[2][2] = 1; //单位矩阵 while (b) { if (b & 1) stu = mul(stu, ans); ans = mul(ans, ans); b >>= 1; } return stu; } int main() { ll n; while (cin >> n) { node cf; memset(cf.m, 0, sizeof(cf.m)); cf.m[0][0] = cf.m[0][1] = cf.m[0][2] = cf.m[1][0] = cf.m[2][1] = 1; if (n == 1) puts("1"); else if (n == 2) puts("2"); else if (n == 3) puts("3"); else { cf = qaq(cf, n - 3); cout << (4 * cf.m[0][0] + 2 * cf.m[0][1] + cf.m[0][2]) % MOD << '\n'; } } return 0; }