51nod 算法馬拉松18 B 非010串 矩陣快速冪，51nod010

51nod 算法馬拉松18 B 非010串 矩陣快速冪，51nod010

非010串

基准時間限制：1 秒 空間限制：131072 KB 分值: 80 如果一個01字符串滿足不存在010這樣的子串，那麼稱它為非010串。 求長度為n的非010串的個數。(對1e9+7取模)   Input

一個數n，表示長度。(n<1e15)

Output

長度為n的非010串的個數。(對1e9+7取模)

Input示例

3

Output示例

7


解釋:
000
001
011
100
101
110
111

    讀完題，這樣的題目肯定是能找到規律所在的，要不然數據太大根本無法算。假設現在給的長度是n，答案為f(n)，那麼假設最後一位是0，前面有010的可能就有f(n-1)種，同樣假設最後一位是1，前面有010的可能就也有f(n-1)，而這樣排除的話還存在著一個問題，就是最後為0的時候可能會出現前面是01而構成010，這樣就加重復了。所以假設前一位為1，再減去f(n-2)，當然還可能前面是11而構成110而不是010，所以還要把多減的再加回來，即再加上一個f(n-3)，這樣一來就可以推出一個公式，f(n)=2*f(n-1)-f(n-2)+f(n-3)。看到這個公式，數據有那麼大，所以我們用矩陣快速冪來進行處理就可以快速得出結果了。

    下面是AC代碼：

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const long long mod=1000000007;

struct matrix
{
    long long a[3][3];
};

matrix cal(matrix A,matrix B)
{
     int i,j,k;
     matrix C;
     for(i=0;i<3;i++)
     {
          for(j=0;j<3;j++)
          {
               C.a[i][j]=0;
               for(k=0;k<3;k++)
               {
                    C.a[i][j]=(C.a[i][j]+(A.a[i][k]*B.a[k][j])%mod+mod)%mod;
               }
          }
     }
     return C;
}

int out(matrix A,matrix B)
{
     cout<<"s:"<<endl;
     cout<<A.a[0][0]<<" "<<A.a[0][1]<<" "<<A.a[0][2]<<endl;
     cout<<A.a[1][0]<<" "<<A.a[1][1]<<" "<<A.a[1][2]<<endl;
     cout<<A.a[2][0]<<" "<<A.a[2][1]<<" "<<A.a[2][2]<<endl;
     cout<<"base:"<<endl;
     cout<<B.a[0][0]<<" "<<B.a[0][1]<<" "<<B.a[0][2]<<endl;
     cout<<B.a[1][0]<<" "<<B.a[1][1]<<" "<<B.a[1][2]<<endl;
     cout<<B.a[2][0]<<" "<<B.a[2][1]<<" "<<B.a[2][2]<<endl;
     return 0;
}

matrix pow_mod(long long x)
{
     matrix s,base;
     base.a[0][0]=2;
     base.a[1][0]=-1;
     base.a[2][0]=1;
     base.a[0][1]=1;
     base.a[1][1]=base.a[2][1]=0;
     base.a[1][2]=1;
     base.a[0][2]=base.a[2][2]=0;
     s.a[0][0]=7;
     s.a[0][1]=4;
     s.a[0][2]=2;
     s.a[1][0]=s.a[1][1]=s.a[1][2]=0;
     s.a[2][0]=s.a[2][1]=s.a[2][2]=0;
     out(s,base);
     while(x)
     {
          if(x&1)
               s=cal(s,base);
          base=cal(base,base);
          out(s,base);
          x>>=1;
     }
     return s;
}

int main()
{
     long long n;
     long long ans;
     while(scanf("%lld",&n)!=EOF)
     {
          if(n==0)
               cout<<0<<endl;
          else if(n==1)
               cout<<2<<endl;
          else if(n==2)
               cout<<4<<endl;
          else if(n==3)
               cout<<7<<endl;
          else
          {
               matrix t=pow_mod(n-3);
               ans=t.a[0][0]%mod;
               cout<<ans<<endl;
               /*cout<<t.a[0][1]%mod<<endl;
               cout<<t.a[1][0]%mod<<endl;
               cout<<t.a[1][1]%mod<<endl;*/
          }
     }
     return 0;
}