\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <duyệt>}}\)

• Liệt kê \(n\) giá trị đầu tiên của dãy rồi sắp xếp theo thứ tự tăng dần, sau đó ta lấy giá trị thứ \(k\)

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(T * n*log(n))\)

\(\color{#300000}{\text{Hint 2 <Quy hoạch động>}}\)

• Nếu ghi dãy số ra thì ta thấy sau một số giá trị thì dãy số lặp lại, với mỗi chu kì thì độ dài không quá \(6 * C\).

• Ta sẽ tìm ra độ dài của chu kì lặp lại, sau đó dùng một mảng \(dp\) để đánh dấu số lần lặp lại trong mỗi chu kì của các giá trị từ \(0\) đến \(C-1\).

• Sau đó ta sẽ nhân các giá trị của \(dp\) cho \(n/dem\) ( \(dem\) là độ dài chu kì ), rồi xử lí thêm \(n\) mod \(dem\) giá trị nữa để tính ra số lần lặp của mỗi giá trị trong \(n\) giá trị đầu tiên. Sau đó ta có thể tính ra giá trị thứ \(k\) dễ dàng.

Lưu ý: Với trường hợp \(C≤A\) hoặc \(C≤B\) thì ta sẽ xét riêng những giá trị này, phần này bạn đọc có thể tự suy nghĩ.

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(T * 6*C)\)

\(\color{#009933}{\text{Preference Accepted Code }}\):

    cin >> n >> C >> k >> a >> b;

    // mảng f tính dem giá trị đầu tiên

    f[1] = a % mod; f[2] = b % mod;

    dp[a % mod]++;dp[b % mod]++;

    for(int i=3; ; i++)
    {
        f[i] = ( f[i-1] + f[i-2] ) % mod;

        dp[f[i]]++;

        if( (f[i] + f[i-1]) %mod == f[1] && (f[i] * 2 + f[i-1]) % mod == f[2])// nếu dãy lặp lại
        {
            dem = i;
            break;
        }
    }
    // xử lí mảng dp
    for(int i=0; i<mod; i++)
        dp[i] *= (n / dem);
    // xử lí thêm n%dem giá trị
    for(int i=1; i <= n % dem; i++)
        dp[f[i]]++;
    //xét nếu a hoặc b >= mod
    if(a >= mod)
        dp[a % mod]--;s.insert(a);
    if(b >= mod)
        dp[b % mod]--;s.insert(b);
    // nếu lấy 1 hoặc 2 giá trị cuối cùng, tùy theo s.size()
    if(n - k < s.size())
    {
        if(n - k == 0)
            cout << *s.rbegin() << endl;
                else cout << *s.begin() << endl;

        return;
    }

    for(int i = 0; i < mod; i++)
        if( dp[i] >= k )
        {
            cout << i << endl;

            return;
        }else k-=dp[i];