51nod 算法马拉松18 B 非010串矩阵快速幂

非010串

基准时间限制：1 秒空间限制：131072 KB 分值: 80

如果一个01字符串满足不存在010这样的子串，那么称它为非010串。

求长度为n的非010串的个数。(对1e9+7取模)

Input

一个数n，表示长度。(n<1e15)

Output

长度为n的非010串的个数。(对1e9+7取模)

Input示例

Output示例

读完题，这样的题目肯定是能找到规律所在的，要不然数据太大根本无法算。假设现在给的长度是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=;

struct matrix

{

    long long a[][];

};

matrix cal(matrix A,matrix B)

{

     int i,j,k;

     matrix C;

     for(i=;i<;i++)

     {

          for(j=;j<;j++)

          {

               C.a[i][j]=;

               for(k=;k<;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[][]<<" "<<A.a[][]<<" "<<A.a[][]<<endl;

     cout<<A.a[][]<<" "<<A.a[][]<<" "<<A.a[][]<<endl;

     cout<<A.a[][]<<" "<<A.a[][]<<" "<<A.a[][]<<endl;

     cout<<"base:"<<endl;

     cout<<B.a[][]<<" "<<B.a[][]<<" "<<B.a[][]<<endl;

     cout<<B.a[][]<<" "<<B.a[][]<<" "<<B.a[][]<<endl;

     cout<<B.a[][]<<" "<<B.a[][]<<" "<<B.a[][]<<endl;

     return ;

}

matrix pow_mod(long long x)

{

     matrix s,base;

     base.a[][]=;

     base.a[][]=-;

     base.a[][]=;

     base.a[][]=;

     base.a[][]=base.a[][]=;

     base.a[][]=;

     base.a[][]=base.a[][]=;

     s.a[][]=;

     s.a[][]=;

     s.a[][]=;

     s.a[][]=s.a[][]=s.a[][]=;

     s.a[][]=s.a[][]=s.a[][]=;

     out(s,base);

     while(x)

     {

          if(x&)

               s=cal(s,base);

          base=cal(base,base);

          out(s,base);

          x>>=;

     }

     return s;

}

int main()

{

     long long n;

     long long ans;

     while(scanf("%lld",&n)!=EOF)

     {

          if(n==)

               cout<<<<endl;

          else if(n==)

               cout<<<<endl;

          else if(n==)

               cout<<<<endl;

          else if(n==)

               cout<<<<endl;

          else

          {

               matrix t=pow_mod(n-);

               ans=t.a[][]%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 ;

}

巴特西

51nod 算法马拉松18 B 非010串矩阵快速幂

最新文章

热门文章

巴特西

51nod 算法马拉松18 B 非010串 矩阵快速幂

最新文章

热门文章

51nod 算法马拉松18 B 非010串矩阵快速幂