首页 > 代码库 > 非010串
非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
思路:矩阵快速幂；
末尾的状态可以看成是01，10，11，00四种状态，那么考虑新加入的是0，和1，进行状态转移，最后矩阵快速幂求解。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<stack> 7 #include<math.h> 8 using namespace std; 9 typedef long long LL; 10 typedef struct node 11 { 12 LL m[4][4]; 13 node() 14 { 15 memset(m,0,sizeof(m)); 16 } 17 } maxtr; 18 const int mod = 1e9+7; 19 maxtr E(); 20 void Init(maxtr *p); 21 maxtr quick_m(maxtr ans,LL m); 22 int main(void) 23 { 24 LL n; 25 scanf("%lld",&n); 26 if(n == 1) 27 printf("2\n"); 28 else if(n == 2) 29 printf("4\n"); 30 else 31 { 32 n-=2; 33 maxtr ak; 34 Init(&ak); 35 maxtr ask = quick_m(ak,n); 36 LL sum = 0; 37 int i ,j; 38 for(i = 0; i < 4; i++) 39 { 40 for(j = 0; j < 4; j++) 41 { //printf("%lld\n",ak.m[i][j]); 42 sum = sum+ask.m[i][j]; 43 sum%=mod; 44 } 45 } 46 printf("%lld\n",sum); 47 } 48 return 0; 49 } 50 maxtr E() 51 { 52 maxtr e; 53 int i,j; 54 for(i = 0; i < 4; i++) 55 { 56 for(j = 0; j < 4; j++) 57 { 58 if(i == j) 59 e.m[i][j] = 1; 60 else e.m[i][j] = 0; 61 } 62 }return e; 63 } 64 void Init(maxtr *p) 65 { 66 memset(p->m,0,sizeof(p->m)); 67 p->m[0][0] = 1; 68 p->m[0][2] = 1; 69 p->m[1][0] = 1; 70 p->m[1][2] = 1; 71 p->m[2][3] = 1; 72 p->m[3][1] = 1; 73 p->m[3][3] = 1; 74 } 75 maxtr quick_m(maxtr ans,LL m) 76 { 77 maxtr C = E(); 78 while(m) 79 { 80 if(m&1) 81 { 82 maxtr dp; 83 for(int i = 0; i < 4; i++) 84 { 85 for(int j = 0; j < 4; j++) 86 { 87 for(int s = 0; s < 4; s++) 88 { 89 dp.m[i][j] = dp.m[i][j] + ans.m[i][s]*C.m[s][j]%mod; 90 dp.m[i][j] %= mod; 91 } 92 } 93 } 94 C = dp; 95 } 96 maxtr ak; 97 for(int i = 0; i < 4; i++) 98 { 99 for(int j = 0; j < 4; j++)100 {101 for(int s = 0; s < 4; s++)102 {103 ak.m[i][j] = ak.m[i][j] + ans.m[i][s]*ans.m[s][j]%mod;104 ak.m[i][j]%=mod;105 }106 }107 }108 ans = ak;109 m/=2;110 }111 return C;112 }
非010串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。