題目:
大家最喜歡的送分題他來了，現在有一個等式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;
}