问题描述
斐波那契串由下列规则生成:
F[0] = “0”;
F[1] = “1”;
F[n] = F[n-1] + F[n-2] (n≥2,+表示连接)
给出一个由0和1构成的串S和一个数n,求出F[n]中S出现的次数。
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。
第二行一个01串S。
输出格式
答案。
样例输入
96
10110101101101
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; }
-
扫码下载安卓APP
-
微信扫一扫关注我们
微信扫一扫打开小程序
手Q扫一扫打开小程序
-
返回顶部
友情链接:
6547题库网 |
Scratch从入门到精通|
Copyright © 小码农 |
2020-2022
发表评论