问题描述
斐波那契串由下列规则生成：
F[0] = “0”;
F[1] = “1”;
F[n] = F[n-1] + F[n-2] （n≥2，+表示连接）
给出一个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。
输入格式
第一行一个数n。
第二行一个01串S。
输出格式
答案。
样例输入
96
10110101101101
样例输出
7540113804746346428
数据规模和约定
n≤263-1，子串长≤10000，答案≤263-1。
参考斐波那契串C++代码如下：
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main(){
long long n;
string s;
cin >> n;
cin >> s;
string a,b,c;
c = "";
a = "0";
b = "1";
int i;
for(i=0;i<n;i++)
{
string::size_type idx;
idx = c.find(s);
if(idx == string::npos)
{
c = b + a;
a = b;
b = c;
}
else
{
break;
}
}
long long start = i-1;
long long x,y;
x =0;
y = 1;
for(int j =start;j<n;j++)
{
long long t = y;
y = y + x;
x = t;
}
cout << y-1;
return 0;
}
发表评论