题目:
大家最喜欢的送分题他来了，现在有一个等式F(n) = F(n - 1) + 2 * F(n - 2) + 3 * F(n - 3)，F(1) = 1, F(2) = 2,F(3) = 3, 现在给出一个n请你求出F(n)对1e9+ 7取模.看到这里你是不是想大喊一声芜湖，起飞，老送分题咯。
输入格式:
简简单单一个n(4 <= n <= 1e9)
输出格式:
输出F(n)对1e9+ 7取模
输入样例:
在这里给出一组输入。例如：
4
输出样例:
在这里给出相应的输出。例如：
10
思路:
这道题类似于斐波那契数列，也是给我们一个递推式和前几项，让我们求第n项，值得注意的是n的范围，
，那说明我们只有通过
的做法才能够通过此题，所以说开数组递推或者是四个变量递推这种
的做法必然会超时的，实测开数组的做法能得8分，四个变量递推能得10分，错误原因都是运行超时，这也是意料之中
那么怎么才能做到
呢？
的算法比较少，常有的有两个，最大公约数和快速幂，这题显然与最大公约数无关，所以这道题用的是快速幂的思想
普通的快速幂是用来求解
% p的问题，是通过倍增底数使得指数减半即:
，这样这个算式就不用执行p次了，我们每次都倍增底数，都能使得指数减半，这种做法的时间复杂度是
的，虽然这题用到的是矩阵快速幂，但本质的思想是一样的
这里我们直接说结论，如下图：
通过对这个矩阵进行幂运算，我们很轻易得就能得到，该递推式的第n项，并成功把复杂度控制了下来，首先矩阵乘法的时间复杂度是
的，一共需要执行logn次，所以该算法的时间复杂度是
的，即便是n取到最大值1e9，log1e9约为30
代码:
//7-18 我是送分题 (30 分)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
struct Matrix //矩阵结构体
{
ll m[3][3]; //3*3的矩阵
Matrix()
{
memset(m , 0 , sizeof m); //通过构造函数初始化矩阵为零矩阵
}
};
Matrix mult(Matrix a , Matrix b) //3*3矩阵的乘法运算
{
Matrix ans;
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
ll sum = 0;
for(int x = 0 ; x < 3 ; x++)
sum = (sum + a.m[i][x] * b.m[x][j]) % MOD;
ans.m[i][j] = sum;
}
}
return ans;
}
Matrix pow(Matrix a , int b) //矩阵快速幂
{
Matrix ans;
ans.m[0][0] = ans.m[1][1] = ans.m[2][2] = 1; //初始化单位矩阵
while(b)
{
if(b & 1)
ans = mult(ans , a);
a = mult(a , a);
b >>= 1;
}
return ans;
}
int main()
{
int n;
Matrix a;
a.m[0][0] = a.m[1][0] = a.m[2][1] = 1; //构造目标矩阵
a.m[0][1] = 2 , a.m[0][2] = 3;
cin>>n;
a = pow(a , n - 3);
ll num[3][1] , ans[3][1];
num[0][0] = 3 , num[1][0] = 2 , num[2][0] = 1; //构造初始矩阵
for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 1 ; j++)
{
ll sum = 0;
for(int x = 0 ; x < 3 ; x++)
sum = (sum + a.m[i][x] * num[x][j]) % MOD;
ans[i][j] = sum;
}
}
cout<<ans[0][0]<<endl;
return 0;
}