Hướng dẫn cho Dãy Fibonacci
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:
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
#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
#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
#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
#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
#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