链接：https://ac.nowcoder.com/acm/problem/14549 来源：牛客网
小d接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
上级领导指示，他只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
小d突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
输入描述: 本题包含多组输入第一行输入一个整数t，表示测试数据的组数 每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量 t<=1000 1<=N<=100000000000000000（10^18） 输出描述: 每组测试数据输出包含一行，表示一共有多少种布置的方式,方案数可能会很大，输出对1000000007取摸的结果。
示例1 输入
2 2 4输出
2 5说明 第一个样例，AA，BB两种方案。 第二个样例，AAAA,BBBB,AABB,ABBA,BBAA五种方案 对于ABBB 因为有连续3个B类型椅子所以不可行
就是有题可得递归公式； 递推公式： f(n) = f( n - 1) + f ( n - 2); 欸嘿，这就和斐波那契相关了，只是初始值不同。f(1)==1；
#include<iostream> #include<cstring> #include<cmath> #include<string> #include<algorithm> #define ll long long using namespace std; const ll mod = 1000000007; struct matrix { ll a[2][2]; }; //这里的mul和pow还有matrix要结合起来用,矩阵快速幂,题目中是有mod的 matrix mul(matrix &x, matrix &y) {//矩阵乘法 matrix c; for (int i = 0; i<2; i++) { for (int j = 0; j<2; j++) { c.a[i][j] = 0; for (int k = 0; k<2; k++) c.a[i][j] = (c.a[i][j] % mod + ((x.a[i][k] % mod) * (y.a[k][j] % mod)) % mod) % mod;//这里需要mod } } return c; } ll pow(matrix x, ll n) {//快速幂 matrix ans; ans.a[0][0] = 1, ans.a[1][0] = 0; ans.a[0][1] = 0, ans.a[1][1] = 1; while (n) { if (n & 1) ans = mul(ans, x); x = mul(x, x); n >>= 1; } return ans.a[0][0]; } int main() { ll n, t; matrix base = { 1, 1, 1, 0 }; /*——————这一部分是初始的矩阵，矩阵的n次，下面的例子使用了 1，1 1，0这个矩阵求出来的就是 斐波那契数，具体用什么函数作为初始函数则 ans.a[0][0]=1,ans.a[1][0]=1; ans.a[0][1]=1,ans.a[1][1]=0; ——————*/ cin >> t; while (t--) { cin >> n; cout << pow(base, n) << endl; } return 0; }