Решение задачи Строки Фибоначчи с Меньшиков

Без пояснения   Просмотров: 30


Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Ограничения: длина S от 1 до 25, 1 <= N <= 45.

Примечание. Длина F(45) равна 1 134 903 170.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
 
using namespace std;
 
int n;
vector<string> mas;
vector<int> calc;
string str;
void input()
{
    cin>>n;
    calc.resize(n);
    cin>>str;
}
void precalc()
{
    int size = 10;
    mas.resize(size);
    mas[0] = "A";
    mas[1] = "B";
    for (int i=2;i<size;i++)
        mas[i] = mas[i-1] + mas[i-2];
}
inline int intersect(int N, string &str)
{
    // F(N) = F(N-1) + F(N-2)
   
    // конец N-1
    int pos = N-1;
    while (pos>=mas.size())
        pos-=2;
    string begin = mas[pos];
   
    // начало N-2
    string end;
    if (N-2 < mas.size())
        end = mas[N-2];
    else
        end = mas.back();
 
    string common = begin + end;
    int left = begin.size() - str.size() + 1;
    left = max(left,0);
 
    int right = min (begin.size()-1, common.size() - str.size());
    for (int i=left; i<=right; i++)
    {
        bool isEqual = true;
        for (int j=0;j<str.size();j++)
        {
            if (common[i+j] != str[j])
            {
                isEqual = false;
                break;
            }
        }
        if (isEqual)
            return 1;
    }
    return 0;
}
void solve()
{
    precalc();
    if (str == "A")
        calc[0] = 1;
    else if (str == "B")
        calc[1] = 1;
    for (int i=2;i<n;i++)
    {
        calc[i] = calc[i-1] + calc[i-2];
        calc[i] += intersect(i,str);
    }
    cout<<calc.back(); 
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться