51nod 2657 二进制数字 斐波那契数列+矩阵快速幂

本文主要是介绍51nod 2657 二进制数字 斐波那契数列+矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2657 二进制数字

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 10 分
6.  
7. 2级题

有多少个长度为n的二进制串，即不存在3个连续的1，也不存在3个连续的0。

例如n = 4，共有16个长度为4的01串，其中0000 0001 1000 1111 0111 1110，不符合要求，所以共有10个符合要求的串。

 收起

输入

输入共1个数n（1 <= n <= 100000)

输出

输出结果mod 1e9+7

输入样例

4

输出样例

10

 

分析：http://www.51nod.com/Question/Index.html#questionId=3613

来自：

当把0换成1后,则又是一个斐波那契。

整个问题变为了，当n足够大时（矩阵快速幂），求2 * f(n)，f(n) = f(n - 1) + f(n - 2)，即两倍的斐波那契数列

 

//矩阵快速幂注意特判
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define N 10005
using namespace std;
const int MAXN= 35;
int p;
typedef long long LL;
int len=35;//构造矩阵的长度
struct Matrix//注意定义的是方阵，*法也是
{LL M[MAXN][MAXN];Matrix(const bool I = 0)  ///初始化对角矩阵{memset(M, 0, sizeof(M));if (I)for(int i = 0; i < len; i++)M[i][i] = 1;}Matrix operator *(const Matrix &y) ///矩阵乘法，对乘法重新定义，z=x*y{Matrix z;for (int i = 0; i < len; i++)//x矩阵的nfor (int j = 0; j < len; j++)//y矩阵的nfor (int k = 0; k < len; k++)//xy矩阵的mz.M[i][j] = (z.M[i][j]+M[i][k]*y.M[k][j])%p;return z;}
};Matrix Pow(Matrix A, long long b)///矩阵的快速幂
{Matrix ans = Matrix(1);for (; b; b>>=1){if (b&1)ans = ans*A;A = A*A;}return ans;
}
Matrix Add(Matrix a,Matrix b)  //a+b
{Matrix c;for(int i = 0; i < len; ++i){for(int j = 0; j < len; ++j){c.M[i][j] =  (a.M[i][j] + b.M[i][j]) % p;}}return c;
}
Matrix MatrixSum(Matrix a,int k)//a + a^2 + a^3 + … + a^k
//原理：等比数列二分求和
{if(k == 1)return a;if(k&1){return Add(MatrixSum(a,k-1),Pow(a,k));  //当n是奇数,f[n]=f[n-1]+A^(n);}else{Matrix E(1);return MatrixSum(a,k>>1)*Add(Pow(a,k>>1),E); //当n是偶数,f[n]=f[n/2]*(A^(n/2)+E);}}
int main()
{LL ans=0;p=1e9+7;scanf("%lld",&ans);if(ans==1){printf("2");return 0;}else if(ans==2){printf("4");return 0;}ans++;Matrix A,B;A.M[0][0]=1;A.M[0][1]=1;A.M[1][0]=1;A.M[1][1]=0; B=Pow(A,ans-2);printf("%lld",(2*(B.M[0][0]+B.M[0][1]))%p);return 0;
}

 

这篇关于51nod 2657 二进制数字 斐波那契数列+矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---