首页 > 代码库 > 51nod 算法马拉松18 B 非010串 矩阵快速幂
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示例
3
Output示例
7
解释:000001011100101110111
读完题，这样的题目肯定是能找到规律所在的，要不然数据太大根本无法算。假设现在给的长度是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;}
51nod 算法马拉松18 B 非010串 矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。