題目描述 Description
Freda要到Rainbow的城堡去玩了。我們可以認為兩座城堡位于同一條數軸上，Freda的城堡坐标是0，Rainbow的城堡坐标是N。正常情況 下，Freda會朝着同一個方向（即Rainbow的城堡相對于Freda的城堡的方向）走若幹步之後來到Rainbow的城堡，而且步長都為1或2。可 是，今天Freda在途中遇見了來自上海的小貓Resodo，驚奇之下，居然有一步走反了方向！不過，Freda并沒有神智不清，它隻有一步走反了方向， 而且這一步的步長也是1或2. 同時，Freda并不會路過Rainbow的城堡而不停下來。當然，Freda是在途中遇到Resodo的，是以它不會在 自己家門口就走錯方向。
舉個例子，如果Rainbow的城堡坐标是3，那麼下面兩條路徑是合法的：
0->1->2->1->3
0->1->-1->1->3
當然，還有其它的合法路徑。下面這些路徑則是不合法的：
0->-1->1->3 （Freda不可能第一步就走錯方向）
0->1->3（Freda一定是有一步走錯方向的）
0->2->1->0->2->3（Freda隻有一步是走錯方向的）
0->-1->0->3（Freda每步的長度一定是1或2）
0->1->2->4->3（Freda不會越過Rainbow的城堡再回來）
0 -> 1 -> 2 -> 3 -> 2 -> 3（Freda一旦到達了Rainbow的城堡，就會停下來）
你現在需要幫助Freda求出，它一共有多少種方法能夠到達Rainbow的城堡呢？
輸入描述 Input Description
一行一個整數N，表示Rainbow城堡的坐标
輸出描述 Output Description
一行一個整數，表示Freda到Rainbow城堡的不同路徑數。由于這個數字可能很大，你隻需要輸出它mod 1000000007的結果。
樣例輸入 Sample Input
2
樣例輸出 Sample Output
5
資料範圍及提示 Data Size & Hint
對于第一組樣例，如下5條路徑是合法的：
0->1->0->2
0->1->-1->0->1->2
0->1->-1->0->2
0->1->0->1->2
0->1->-1->1->2
資料範圍與約定
對于10%的資料，N<=20.
對于70%的資料，N<=1000.
對于90%的資料，N<=1000000.
對于100%的資料，N<=10^15.
題解：
這是一個比較典型的用矩陣乘法優化狀壓動規的題。
先來寫一下dp方程。
設f[i][0]表示走到點i并且途中沒有轉過的路徑數。
設f[i][1]表示走到點i并且途中轉過一次的路徑數。
先考慮f[i][0]
可以發現f[i][0]其實就是斐波那契數列。
即f[i][0]=f[i-1][0]+f[i-2][0] (i>=3);
然後考慮f[i][1];
可以發現f[i][1]隻有兩種情況
1.從這個點的前面走過來，即從f[i-1][1]或f[i-2][1]走過來
2.從這個點的後面轉回來，由于隻準轉一次，并且隻能轉一步或兩步，是以隻能從f[i+1][0]或f[i+2][0]轉回來
綜合1，2可知f[i][1]=f[i-1][1]+f[i-2][1]+f[i+1][0]+f[i+2][0] (i>=3);
接着我們就可以dp了
時間複雜度O(n);
這樣我們可以通過90%的資料。
100%的資料需要使用矩陣乘法優化。。
我們可以發現其實我們要求的隻有f[i][1]，而f[i][1]隻與
f[i-1][1]，f[i-2][1]，f[i+1][0]，f[i+2][0]有關
其中f[i-1][1]正好是f[i][1]的前一項，這樣很明顯可以使用矩陣乘法轉移狀态；
構造如下矩陣：
⎡⎣⎢⎢⎢1001111011001000⎤⎦⎥⎥⎥ ×⎡⎣⎢⎢⎢⎢f[i−1][1]f[i+2][0]f[i+1][0]f[i−2][1]⎤⎦⎥⎥⎥⎥ = ⎡⎣⎢⎢⎢⎢f[i][1]f[i+3][0]f[i+2][0]f[i−1][1]⎤⎦⎥⎥⎥⎥
這樣給定一個n(n>=3)我們隻需要求出第一個矩陣的n-2次方
再乘上
⎡⎣⎢⎢⎢⎢f[2][1]f[5][0]f[4][0]f[1][1]⎤⎦⎥⎥⎥⎥ 即可
代碼:
#include<iostream>
#include<cstdio>
#define m 1000000007
using namespace std;
long long ans[][],aa[][],n,sum,t;
bool f;
inline long long cheng(long long a,long long b)
{
long long ans();
a=a%m;
while (b>)
{
if (b%==)
ans=(ans+a)%m;
b/=;
a=(a*)%m;
}
return ans;
}
inline void power(long long x)
{
long long k[][];
while (x>)
{
if (x%==)
{
if (f==false)
{
for (int i=;i<=;i++)
for (int j=;j<=;j++)
ans[i][j]=aa[i][j];
f=true;
}
else
{
for (int i=;i<=;i++)
for (int j=;j<=;j++)
{
k[i][j]=;
for (int p=;p<=;p++)
k[i][j]=(k[i][j]+cheng(ans[i][p],aa[p][j]))%m;
}
for (int i=;i<=;i++)
for (int j=;j<=;j++)
ans[i][j]=k[i][j];
}
}
x/=;
for (int i=;i<=;i++)
for (int j=;j<=;j++)
{
k[i][j]=;
for (int p=;p<=;p++)
k[i][j]=(k[i][j]+cheng(aa[i][p],aa[p][j]))%m;
}
for (int i=;i<=;i++)
for (int j=;j<=;j++)
aa[i][j]=k[i][j];
}
}
int main()
{
cin>>n;
if (n==)
{
cout<<<<endl;
return ;
}
if (n==)
{
cout<<<<endl;
return ;
}
f=false;
aa[][]=;aa[][]=;aa[][]=;aa[][]=;
aa[][]=;aa[][]=;aa[][]=;aa[][]=;
aa[][]=;aa[][]=;aa[][]=;aa[][]=;
aa[][]=;aa[][]=;aa[][]=;aa[][]=;
power(n-);
sum=(cheng(ans[][],)+cheng(ans[][],)+cheng(ans[][],)+cheng(ans[][],))%m;
printf("%lld\n",sum);
}