Hướng dẫn cho Dãy Fibonacci

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: kitsune

Gọi \(m\) là số lượng số Fibonacci không vượt quá tổng của dãy. Vì hàm Fibonacci là một hàm tăng rất nhanh nên \(m\) sẽ rất nhỏ (Ở subtask cuối \(m\) chỉ khoảng \(67\)).

Subtask \(1\):

Tutorial

Ta sinh tất cả các cách chia dãy và kiểm tra xem tổng mỗi dãy con có phải là một số Fibonacci hay không và cập nhật đáp án.

Độ phức tạp: \(O(2^n \cdot n \cdot m)\).

Solution

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 2;
const int MOD = 1e9 + 7;

int n, a[MAX];
bool b[MAX];
int ans;

bool is_Fibonacci(long long sum) {
    long long f_1 = 0, f_2 = 1, f_n;
    do {
        f_n = f_1 + f_2;
        if (f_n == sum) {
            return true;
        }

        f_1 = f_2;
        f_2 = f_n;
    } while (f_n < sum);

    return false;
}

bool check() {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (b[i]) {
            if (!is_Fibonacci(sum)) {
                return false;
            }

            sum = 0;
        }
    }

    return is_Fibonacci(sum);
}

void backtrack(int i) {
    if (i == n) {
        ans += check();
        return;
    }

    backtrack(i + 1);
    b[i] = 1;
    backtrack(i + 1);
    b[i] = 0;
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    backtrack(1);

    cout << ans << "\n";

    return 0;
}

Subtask \(2\):

Tutorial

Ta sử dụng quy hoạch động.

Gọi \(\text{dp}(i)\) là số lượng cách chia dãy \(a[1 \ldots i]\) thành các dãy con gồm các phần tử liên tiếp sao cho tổng của mỗi dãy con là một số Fibonacci. Ta có công thức quy hoạch động là:

\(\displaystyle \text{dp}(i) = \sum_{j = 1}^{i} \text{dp}(j - 1)\) với tổng \(a[j \ldots i]\) là một số Fibonacci

Trường hợp cơ sở là \(\text{dp}(0) = 1\), đáp án của bài toán là \(\text{dp}(n)\).

Vậy ta có thể duyệt \(i\) từ \(1\) đến \(n\) và duyệt \(j\) từ \(i\) về \(1\) để dễ dàng tính tổng \(a[j \ldots i]\) giá trị \(\text{dp(i)}\).

Độ phức tạp: \(O(n^2 \cdot m)\).

Solution

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 2;
const int MOD = 1e9 + 7;

int n, a[MAX];
int dp[MAX];

bool is_Fibonacci(long long sum) {
    long long f_1 = 0, f_2 = 1, f_n;
    do {
        f_n = f_1 + f_2;
        if (f_n == sum) {
            return true;
        }

        f_1 = f_2;
        f_2 = f_n;
    } while (f_n < sum);

    return false;
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j >= 1; j--) {
            sum += a[j];
            if (is_Fibonacci(sum)) {
                dp[i] += dp[j - 1];
                dp[i] %= MOD;
            }
        }
    }

    cout << dp[n] << "\n";

    return 0;
}

Subtask \(3\):

Tutorial

Vì mỗi phần tử là một số nguyên dương và nên nếu \(j\) càng giảm thì tổng \(a[j \ldots i]\) càng tăng nên ta có thể sử dụng tổng tiền tố kết hợp với cấu trúc dữ liệu std::map hay thuật toán như tìm kiếm nhị phân, hai con trỏ để tìm tất cả \(j\) thoả mãn.

Độ phức tạp: \(O(n \cdot \log n \cdot m)\) hay \(O(n \cdot m)\) tuỳ vào cách cài đặt.

Solution

std::map

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 2;
const int MOD = 1e9 + 7;

int n, a[MAX];
int dp[MAX];

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

    cin >> n;

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        sum += a[i];
    }

    vector <long long> Fibonacci;
    long long f_1 = 0, f_2 = 1, f_n;
    do {
        f_n = f_1 + f_2;
        Fibonacci.push_back(f_n);

        f_1 = f_2;
        f_2 = f_n;
    } while (f_n < sum);

    map <long long, int> idx;
    sum = 0;
    idx[0] = 0;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        for (auto x : Fibonacci) {
            if (idx.count(sum - x)) {
                dp[i] += dp[idx[sum - x]];
                dp[i] %= MOD;
            }
        }

        idx[sum] = i;
    }

    cout << dp[n] << "\n";

    return 0;
}

Binary Search

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 2;
const int MOD = 1e9 + 7;

int n;
long long p[MAX];
int dp[MAX];

long long sum(int l, int r) {
    return p[r] - p[l - 1];
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> p[i];

        p[i] += p[i - 1];
    }

    vector <long long> Fibonacci;
    long long f_1 = 0, f_2 = 1, f_n;
    do {
        f_n = f_1 + f_2;
        Fibonacci.push_back(f_n);

        f_1 = f_2;
        f_2 = f_n;
    } while (f_n < p[n]);

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int last_j = i;
        for (auto x : Fibonacci) {
            int j = -1;
            for (int lb = 1, rb = last_j; lb <= rb; ) {
                int mb = (lb + rb) / 2;

                if (sum(mb, i) >= x) {
                    j = mb;
                    lb = mb + 1;
                } else {
                    rb = mb - 1;
                }
            }

            if (j == -1) {
                break;
            }

            if (sum(j, i) == x) {
                dp[i] += dp[j - 1];
                dp[i] %= MOD;
            }

            last_j = j;
        }
    }

    cout << dp[n] << "\n";

    return 0;
}

Two pointers

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 2;
const int MOD = 1e9 + 7;

int n;
long long p[MAX];
int idx[MAX], dp[MAX];

long long sum(int l, int r) {
    return p[r] - p[l - 1];
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> p[i];

        p[i] += p[i - 1];
    }

    vector <long long> Fibonacci;
    long long f_1 = 0, f_2 = 1, f_n;
    do {
        f_n = f_1 + f_2;
        Fibonacci.push_back(f_n);

        f_1 = f_2;
        f_2 = f_n;
    } while (f_n < p[n]);

    for (int i = 0; i < (int)Fibonacci.size(); i++) {
        idx[i] = 1;
    }

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (int)Fibonacci.size(); j++) {
            while (sum(idx[j] + 1, i) >= Fibonacci[j]) {
                idx[j]++;
            }

            if (sum(idx[j], i) == Fibonacci[j]) {
                dp[i] += dp[idx[j] - 1];
                dp[i] %= MOD;
            }
        }
    }

    cout << dp[n] << "\n";

    return 0;
}

Bình luận

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