LQDFIBO - Xâu Fibonacci

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <utility>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int MOD = 1e9;
using namespace std;
string S[20];
string P;
int lim;

typedef vector<int> big;

big operator + (big a, big b) {
    big c; int carry = 0;
    FOR(i, 0, max(SZ(a), SZ(b))) {
        if (i < SZ(a)) carry += a[i];
        if (i < SZ(b)) carry += b[i];
        c.PB(carry % MOD);
        carry /= MOD;
    }
    if (carry) c.PB(carry);
    return c;
}

void PRINT(big a) {
    cout << a[SZ(a) - 1];
    REPD(i, SZ(a) - 2, 0)
        printf("%09d", a[i]);
    cout << endl;
}

int Occ(string S, string P) {
    int cnt = 0;
    REP(i, 0, SZ(S) - SZ(P))
        cnt += S.substr(i, SZ(P)) == P;
    return cnt;
}

const int N = 1010;
big F[N]; int M[20][20];
int n;

int main() {
    cin >> n; cin >> S[1]; cin >> S[2]; cin >> P;
    FOR(i, 3, 20) {
        S[i] = S[i - 1] + S[i - 2];
        if (SZ(S[i - 1]) >= 100) {
            lim = i; break;
        }
    }
    FOR(i, lim + 1, 20) S[i] = S[i - 1] + S[i - 2];
    if (n < 20) cout << Occ(S[n], P);
    else {
        REP(i, 1, lim + 4) F[i].PB(Occ(S[i], P));
        REP(i, lim - 1, lim) REP(j, lim - 1, lim) {
            M[i][j] = Occ(S[i] + S[j], P) - F[i][0] - F[j][0];
        }
        REP(i, lim + 5, n) {
            big tmp; tmp.PB(M[lim - (i & 1)][lim]);
            F[i] = F[i - 1] + F[i - 2] + tmp;
        }
        PRINT(F[n]);
    }
    return 0;
}

Download