Submission #5121311

---

Source Code Expand

#include <bits/stdc++.h>

#define ALL(a) (a).begin(), (a).end()
#define llong long long

using namespace std;

vector<int> fib(25, -1);
int calc_Fib(int n){
	if(fib[n] != -1)return fib[n];
	return calc_Fib(n-1) + calc_Fib(n-2);
}

vector<int> g(25,-1);
int calc(const int n, const string &str, const size_t l, const size_t r){
	if(g[n] != -1) return g[n];
//	cerr << n << endl;
	assert(n >= 3);
	if(n == 3){
		if(str[l] == 'b') g[3] = 1;
		else g[3] = 0;
		return g[3];
	}
	bool flag1 = true, flag2 = true;
	for(size_t i = 0; i < fib[n-2]; i++){
		if(str[l+i] != str[l+fib[n-2]+i] ){
			flag1 = false;
		}
		if(str[l+i] != str[l+fib[n-1]+i]){
			flag2 = false;
		}
	}
	if(flag1 || flag2){
		return 1 + calc(n-1, str, l+fib[n-2], r) * 2;
	}
	return calc(n-1, str, l, r+fib[n-1])*2;
	
}

signed main(){
	fib[1] = 1; fib[2] = 1;
	for(int i = 3; i < 25; i++)fib[i] = calc_Fib(i);
	g[2] = 0;
	g[1] = 0;
	string s; cin >> s;
	int n;
	for(int i = 2; i < 25; i++){
		if(fib[i] == s.size()){
			n = i;
			break;
		}
	}
	cout << n << " " << calc(n, s, 0, s.size()) << endl;
	

	return 0;
}

Submission Info

Judge Result