Hướng dẫn cho LQDOJ CUP 2022 - Round 8 - LISFIBO

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: nhphucqt

Subtask \(1\) (\(15\%\) số điểm): \(n \leq 10^3\).

Tutorial

Tạo dãy \(F_1, F_2, \ldots, F_n\). Sau đó quy hoạch động gọi \(dp[i]\) là dãy con không giảm dài nhất kết thúc tại vị trí \(i\). Công thức như sau:

\[ dp[i] = \max\left(1, \displaystyle\max_{\substack{1 \leq \, j \, < \, i, \\ F_j \, \leq \, F_i}}\left(dp[j] + 1\right)\right) \]

Độ phức tạp: \(\mathcal{O}\left(n^2\right)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1005;

int n, mod;
int fibonacci[MAX_N], dp[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("LISFIBO.inp", "r", stdin);
    freopen("LISFIBO.out", "w", stdout);

    cin >> n >> mod;

    fibonacci[1] = 1;
    fibonacci[2] = 1;
    for (int i = 3; i <= n; ++i) {
        fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % mod;
    }

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (fibonacci[j] <= fibonacci[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }

    cout << res << '\n';

    return 0;
}

Subtask \(2\) (\(15\%\) số điểm): \(n \leq 10^6\).

Tutorial

Sử dụng ý tưởng của subtask 1 tuy nhiên cần dùng Fenwick Tree để cải tiến độ phức tạp.
Độ phức tạp: \(\mathcal{O}\left(n \cdot \log n \right)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000005;

struct FenwickTree {
    int treeSize;
    vector<int> nodes;

    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
    }

    void update(int id, int val) {
        for (++id; id <= treeSize; id += (id & -id)) {
            nodes[id] = max(nodes[id], val);
        }
    }

    int get(int id) {
        int result = 0;
        for (++id; id >= 1; id -= (id & -id)) {
            result = max(result, nodes[id]);
        }
        return result;
    }
};

int n, mod;
int fibonacci[MAX_N];
FenwickTree fenwickTree;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("LISFIBO.inp", "r", stdin);
    freopen("LISFIBO.out", "w", stdout);

    cin >> n >> mod;

    fibonacci[1] = fibonacci[2] = 1;
    for (int i = 3; i <= n; ++i) {
        fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % mod;
    }

    fenwickTree.init(mod + 1);
    for (int i = 1; i <= n; ++i) {
        fenwickTree.update(fibonacci[i], fenwickTree.get(fibonacci[i]) + 1);
    }

    cout << fenwickTree.get(mod) << '\n';

    return 0;
}

Subtask \(3\) (\(20\%\) số điểm): \(M \leq 3\).

Tutorial

Với \(M = 1\): xét trường hợp \(n = 1\), \(n = 2\), \(n = 3\) và \(n > 3\).
Với \(M = 2\): nhận thấy ta sẽ chọn dãy gồm toàn số \(1.\)
Với \(M = 3\): bạn nhận thấy dãy tạo được có chu trình \([1,1,2,0,2,2,1,0]\) và dãy không giảm dài nhất cần tìm sẽ bắt đầu từ giá trị \(1\) và kết thúc bởi tối đa \(3\) giá trị \(2\). Ví dụ với \(n = 6\) thì kết quả là \(5\).

Độ phức tạp: \(\mathcal{O}\left(1\right)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

long long n;
int mod;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("LISFIBO.inp", "r", stdin);
    freopen("LISFIBO.out", "w", stdout);

    cin >> n >> mod;

    if (mod == 1) {
        if (n <= 3) {
            cout << min(n, 2LL);
        } else {
            cout << n - 2;
        }
    } else if (mod == 2) {
        cout << (n / 3) * 2 + (n % 3);
    } else {
        int siz = 8;
        int period[siz] = {1, 1, 2, 0, 2, 2, 1, 0};
        long long num = n / siz;
        int rem = n % siz;
        long long res = num * 3;
        if (num > 0 && rem <= 2) {
            res += 2;
        } else {
            for (int i = 0, cur = 1; i < rem; ++i) {
                res += cur <= period[i];
                cur = max(cur, period[i]);
            }
        }
        cout << res;
    }

    return 0;
}

Subtask \(4\) (\(25\%\) số điểm): \(M \leq 45\).

Tutorial

Ở subtask 4 này bạn sẽ khảo sát và thấy được việc tạo thành chu trình của một dãy Fibonacci theo một Modulo. Đối với \(M \le 45\) thì chu trình tạo được không vượt quá \(122.\) Giả sử dãy tạo được từ việc viết lặp lại liên tiếp các dãy \(C\) (độ dài của \(C \le 122\) như đã nói). Trên dãy \(C\) này ta có thể quy hoạch động \(f[x,y]\) là độ dài dãy con không giảm dài nhất bắt đầu từ giá trị không nhỏ hơn \(\mathbb{x}\) và kết thúc tại giá trị không lớn hơn \(\mathbb{y}\) trong một dãy \(C\).
Sau đó, gọi \(dp[i,x,y]\) là dãy con không giảm dài nhất bắt đầu từ giá trị không nhỏ hơn \(\mathbb{x}\) và kết thúc tại giá trị không lớn hơn \(\mathbb{y}\) xét trên dãy mà dãy \(C\) được viết lặp lại \(i\) lần liên tiếp.
Ta có công thức:

\[dp[i,x,y] = \max_{x \leq z \leq y} (dp[i - 1,x,z] + f[z, y])\]

Nhận thấy \(n \le 10^{18}\) tức là ta sẽ viết liên tiếp rất nhiều lần dãy \(C\) nên không thể quy hoạch động như thông thường. Do đó ta sẽ quy hoạch động nhân ma trận (lấy min/max, tương tự với lấy sum). Lưu ý, sau đó bạn cần xét thêm phần dư ở cuối dãy Fibonacci và update vào kết quả.
Độ phức tạp: \(\displaystyle \mathcal{O}\left(\left|C\right|^3 \cdot \log\frac{n}{|C|}\right)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 150;

long long S;
int n, mod;
int fibonacci[MAX_N];

struct Matrix {
    int n;
    long long c[MAX_N][MAX_N];

    Matrix() {
        memset(c, -0x3f, sizeof c);
    }

    Matrix(int nn) {
        n = nn;
        memset(c, -0x3f, sizeof c);
    }

    void toUnit() {
        memset(c, -0x3f, sizeof c);
        for (int i = 1; i <= n; ++i) {
            c[i][i] = 0;
        }
    }

    Matrix operator*(const Matrix &ma) const {
        Matrix res(n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 1; k <= n; ++k) {
                    res.c[i][j] = max(res.c[i][j], c[i][k] + ma.c[k][j]);
                }
            }
        }
        return res;
    }

    void operator*=(const Matrix &ma) {
        *this = *this * ma;
    }
} f, base;

Matrix myPow(Matrix a, long long n) {
    Matrix res(a.n);
    res.toUnit();
    for (; n; n >>= 1, a *= a) {
        if (n & 1) {
            res *= a;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("LISFIBO.inp", "r", stdin);
    freopen("LISFIBO.out", "w", stdout);

    cin >> S >> mod;

    if (mod == 1) {
        if (S <= 3LL) {
            return cout << min(S, 2LL), 0;
        } else {
            return cout << S - 2, 0;
        }
    }

    n = 3;
    fibonacci[1] = fibonacci[2] = 1;
    for (;; ++n) {
        fibonacci[n] = (fibonacci[n - 2] + fibonacci[n - 1]) % mod;
        if (fibonacci[n - 1] == 1 && fibonacci[n] == 1) {
            n -= 2;
            break;
        }
    }

    base.n = n;
    for (int i = 1; i <= n; ++i) {
        base.c[i][i] = 1;
        for (int j = i - 1; j >= 1; --j)
            if (fibonacci[j] <= fibonacci[i]) {
                for (int k = j; k < i; ++k)
                    if (fibonacci[j] <= fibonacci[k] && fibonacci[k] <= fibonacci[i]) {
                        base.c[j][i] = max(base.c[j][i], base.c[j][k] + 1);
                    }
            }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            if (fibonacci[j] <= fibonacci[i]) {
                for (int k = 1; k <= i; ++k) {
                    if (fibonacci[j] <= fibonacci[k] && fibonacci[k] <= fibonacci[i]) {
                        base.c[j][i] = max(base.c[j][i], base.c[k][i]);
                    }
                }
            }
    }

    f = myPow(base, S / n);
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            res = max(res, f.c[j][i]);
        }
    }
    f *= base;

    int rem = S % n;
    for (int i = 1; i <= rem; ++i) {
        for (int j = 1; j <= n; ++j) {
            res = max(res, f.c[j][i]);
        }
    }

    cout << res;
    return 0;
}

Subtask \(5\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Tương tự subtask 4. Đối với \(M \leq 1000\) thì chu trình tạo được không vượt quá \(3000\). Giả sử dãy tạo được từ việc viết lặp lại liên tiếp các dãy \(C\) (độ dài của \(C \leq 3000\) như đã nói).
Đặt \(L\) là độ dài dãy \(C\).
Gọi \(T\) là số lượng dãy \(C\) được viết liên tiếp (\(T\) xấp xỉ \([n / L]\)).
Case 1: Số lượng dãy \(C\) được viết liên tiếp không lớn hơn \(2L\). Khi đó, ta có \(n \leq 2L^2\). Ta có thể làm như subtask 2.
Case 2: Số lượng dãy \(C\) được viết liên tiếp lớn hơn \(2L\). Nhận xét và chứng minh được rằng tồn tại một kết quả tối ưu mà dãy chỉ có thể tăng ngặt ở \(L\) dãy \(C\) đầu tiên và \(L\) dãy \(C\) cuối cùng. Còn \(T - 2L\) dãy \(C\) ở giữa sẽ có các giá trị bằng nhau. Việc chứng minh xin nhường lại bạn đọc!
Từ đó ta xây dựng \(left[x]\) là độ dài dãy con không giảm dài nhất kết thúc tại giá trị không lớn hơn \(\mathbb{x}\) trong \(L\) dãy \(C\) đầu tiên. Tương tự tạo \(right[x]\) là độ dài dãy con không giảm dài nhất bắt đầu tại giá trị không nhỏ hơn \(\mathbb{x}\) trong \(L\) dãy \(C\) cuối cùng (tính thêm cả phần dư). Việc chuẩn bị này sẽ mất \(O(L^2 \cdot \log(L))\). Sau khi chuẩn bị xong, ta sẽ duyệt giá trị \(x\) bằng nhau ở \(T - 2L\) dãy \(C\) liên tiếp ở giữa, có bao nhiêu giá trị cộng thêm với \(left[x] + right[x]\) để so sánh với kết quả hiện có.
Độ phức tạp: \(\mathcal{O}\left(\left|C\right|^2 \cdot \log M \right)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3005;
const int MAX = 1005;
const int SIZE = MAX_N * MAX_N * 2 + MAX_N;

struct FenwickTree {
    int treeSize;
    vector<int> nodes;

    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
    }

    void update(int id, int val) {
        for (++id; id <= treeSize; id += (id & -id)) {
            nodes[id] = max(nodes[id], val);
        }
    }

    int get(int id) {
        int result = 0;
        for (++id; id >= 1; id -= (id & -id)) {
            result = max(result, nodes[id]);
        }
        return result;
    }
};

long long S;
long long pref[MAX_N], suff[MAX_N];
int n, mod, rem;
int fibonacci[SIZE], cnt[MAX];
FenwickTree fenwickTree;

int bruteforce() {
    fenwickTree.init(mod);
    for (int i = 1; i <= S; ++i) {
        fenwickTree.update(fibonacci[i], fenwickTree.get(fibonacci[i]) + 1);
    }
    return fenwickTree.get(mod - 1);
}

long long lis() {
    fenwickTree.init(mod);
    for (int i = 1; i <= n * n; ++i) {
        int id = i % n == 0 ? n : i % n;
        pref[id] = fenwickTree.get(fibonacci[i]) + 1;
        fenwickTree.update(fibonacci[i], pref[id]);
    }
    fenwickTree.init(mod);
    for (int i = n * n + rem; i >= 1; --i) {
        int id = i % n == 0 ? n : i % n;
        suff[id] = fenwickTree.get(mod - fibonacci[i] - 1) + 1;
        fenwickTree.update(mod - fibonacci[i] - 1, suff[id]);
    }
    for (int i = 1; i <= n; ++i) {
        cnt[fibonacci[i]]++;
    }
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        long long mxPref = 0, mxSuff = 0;
        for (int j = 1; j <= n; ++j) {
            if (fibonacci[j] <= fibonacci[i]) {
                mxPref = max(mxPref, pref[j]);
            }
        }
        for (int j = 1; j <= n; ++j) {
            if (fibonacci[i] <= fibonacci[j]) {
                mxSuff = max(mxSuff, suff[j]);
            }
        }
        res = max(res, mxPref + mxSuff + (S / n - 2 * n) * cnt[fibonacci[i]]);
    }
    return res;
}

int findPeriod(int n) {
    int a = 1, b = 1, cnt = 0;
    do {
        cnt++;
        a = (a + b) % n;
        swap(a, b);
    } while (a != 1 || b != 1);
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("LISFIBO.inp", "r", stdin);
    freopen("LISFIBO.out", "w", stdout);

    cin >> S >> mod;

    if (mod == 1) {
        if (S <= 3LL) {
            return cout << min(S, 2LL), 0;
        } else {
            return cout << S - 2, 0;
        }
    }

    n = findPeriod(mod);
    rem = S % n;

    fibonacci[1] = fibonacci[2] = 1;
    for (int i = 3; i <= n * n * 2 + rem; ++i) {
        fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % mod;
    }

    if (S <= n * n * 2 + rem) {
        cout << bruteforce() << '\n';
    } else {
        cout << lis() << '\n';
    }

    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.