试题 算法训练 斐波那契串

问题描述

斐波那契串由下列规则生成：
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。

#include<iostream>
#include<string>
using namespace std;

string s;
string s1 = "0";
string s2 = "1";
string s0;
long long n;
long long ans1, ans2, ans;

int main() {
	cin >> n;
	
	cin >> s;
	
	for (int i = 2; i <= 23; i ++) {
		s0 = s2 + s1;
		s1 = s2;
		s2 = s0;
	}
	
	for (int i = 0; i <= (s0.size() - s.size()); i ++) {
		if (s == s0.substr(i, s.size())) {
			ans1 ++;
		}
	}
	
	s0 = s2 + s1;
	s1 = s2;
	s2 = s0;
	
	for (int i = 0; i <= (s0.size() - s.size()); i ++) {
		if (s == s0.substr(i, s.size())) {
			ans2 ++;
		}
	}
	
	for (int i = 25; i <= n; i ++) {
		ans = ans1 + ans2 + 1;
		ans1 = ans2;
		ans2 = ans;
	}
	
	cout << ans;
	
	return 0;
}

总结：

如果直接找是找不到，太大了，找规律

先找能找到的，比如n=23的时候，有几个s，n=24的时候有几个s

因为s本就是斐波那契串的一部分，所以它的数量也是符合斐波那契串的规律，当找到两个的时候，就能通过这两个找到下一个，然后一直循环到n

但是long long如果在main中声明，就会出错

但是在全局中声明，答案就是对的