데이터 구조 서론 이 다른 fibonacci 수열

★ 실험 의뢰 Winder 는 최근 fibonacci 수열 에 관 한 지식 을 배우 고 있다.우 리 는 모두 fibonacci 수열 의 전달 공식 이 F (n) = F (n - 1) + F (n - 2) (n > = 2 이 고 n 은 정수) 라 는 것 을 안다.Winder 가 알 고 싶 은 것 은 우리 가 이 전달 식 을 F (n) = AF (n - 1) + BF (n - 2) (n > = 2 와 n 을 정수 로 바 꿀 때 우리 가 얻 은 수열 이 무엇 인지 입 니 다.하지만 윈 더 는 게 을 러 서 네가 그 를 도와 이 일 을 완성 할 수 밖 에 없다.여기 서 우 리 는 여전히 F (0) = F (1) = 1 을 명령 합 니 다.★ 데이터 입력 입력 은 첫 줄 의 세 개의 정수 N, A 와 B (N < = 10; 1 < = A, B < = 100 이 고 모두 정수) 를 입력 합 니 다.다음은 N 줄 이 있 습 니 다. 줄 마다 자연수 n (n < = 100000000) 이 있 습 니 다.★ 데이터 출력 은 한 줄 한 줄 의 정수 F (n) 를 출력 합 니 다. 결과 가 클 수 있 기 때문에 Winder 는 출력 결 과 를 2013 에 모델 링 하 라 고 요구 합 니 다.
분석: 처음에 이 문 제 를 보 았 을 때 1e8 의 데 이 터 는 폭력 이 해결 되 지 않 을 것 이 라 고 예상 했다. 그러나 폭력 이 었 다. 그 결과 모든 TLE 는 fib 배열 이 중복 성 이 있 을 수 있다 는 것 을 고려 했다. 2013 년 에 모델 링 을 했 기 때문에 fib [i] 는 fib [i - 1] 와 fib [i - 2] 에 달 려 있다. 분명히 두 숫자 가 연속 적 으로 같 으 면 무슨 뜻 이 있 을 까?
예 를 들 어 1, 2, 3, 4, 1, 2. 여기 1, 2 와 뒤에 1, 2 가 똑 같 습 니 다. 전체 서열 이 1, 2, 3, 4, 1, 2, 3, 4.........................................
set 의 판정 중 근 거 는 < 연산 자의 과부하 입 니 다.
이 시간의 복잡 도 는 4e6 의 데이터 양 에 있어 서 가능 하 다.알고리즘 은 아래 와 같다.

#include
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define INF 0X7fffffff
using namespace std;
const int maxn = 5e6 + 10;
const int MOD = 2013;
LL fib[maxn];
struct node {
    int a, b;
    int pos;
    node(int a, int b, int pos): a(a), b(b), pos(pos){}
    node(){}
    friend bool operator < (const node& n1, const node& n2) {
        return n1.a != n2.a || n1.b != n2.b;
    }
};

set<node> ss;


/*
F（n）=AF（n-1）+BF（n-2）（n>=2 n   ） F（0）= F（1）=1。
n <= 100000000 MOD 2013
*/

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL a, b, t;
    cin >> t >> a >> b;
    fib[0] = fib[1] = 1;
    ss.insert(node(1, 1, 1));
    int circle;
    int first;
    for(int i = 2; i <= maxn; i++) {
        fib[i] = (a * fib[i - 1] + b * fib[i - 2]) % MOD;
        //cout << fib[i] << " " << fib[i - 1] << endl;
        node n(fib[i - 1], fib[i], i);
        if(ss.count(n)) {
            // cout << fib[i - 1] << " " << fib[i] << endl;
            // cout << ss.find(n) -> a << " " << ss.find(n) -> b << endl;
            first = ss.find(n) -> pos;
            circle = i - ss.find(n) -> pos;
            //cout << first << " " << circle << endl;
            break;
        }
        ss.insert(n);
    }
    while(t--) {
        cin >> a;
        if(a <= first) cout << fib[a] << endl;
        else {
            a = (a - first) % circle + first;
            cout << fib[a] << endl;
        }
    }
    return 0;
}