小码农

趣味编程-面向每个人的创意编程
问题描述
  斐波那契串由下列规则生成:
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;
}

 

发表评论