Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int M1 = 1000000003;
const int M2 = 1000000007;
const int M3 = 1000000009;
const int N = 1000006;
const int NN = N + N + N;
using namespace std;
int n;
char a[N];

struct Hash {
    int H1, H2, H3;
    Hash() {}
    Hash(int a, int b, int c) {H1 = a % M1; H2 = b % M2; H3 = c % M3;}
    Hash operator + (const Hash &a)
        {return Hash(a.H1 + H1, a.H2 + H2, a.H3 + H3);}
    bool operator < (const Hash &a) const
        {return (H1 != a.H1) ? (H1 < a.H1) : ((H2 != a.H2) ? (H2 < a.H2) : H3 < a.H3);}
};
Hash F[NN];

int MOD(int M) {
    int r = 0;
    for(int i = 0; a[i]; i++)
        r = (10ll * r + a[i] - '0') % M;
    return r;
}

int main()
{
    F[0] = F[1] = Hash(1, 1, 1);
    for(int i = 2; i < NN; i++) F[i] = F[i - 1] + F[i - 2];
    sort(F, F + NN);
    scanf("%d\n", &n);
    while (n--) {
        scanf("%s\n", a);
        printf("%s\n", binary_search(F, F + NN, Hash(MOD(M1), MOD(M2), MOD(M3))) ? "Yes" : "No");
    }
    return 0;
}