Hướng dẫn giải của Số cách khôi phục mảng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, ,
Hiểu bài toán
Cho một mảng gồm n phần tử. Mỗi phần tử là một số nguyên thuộc đoạn [l, r]. Yêu cầu đếm số cách chọn mảng sao cho tổng всех các phần tử chia hết cho 3. Kết quả cần in ra số dư khi chia cho $10^9 + 7$. Dữ liệu đầu vào: $1 \le n \le 10^6$, $1 \le l \le r \le 10^9$. Do $n$ và $r$ khá lớn, các thuật toán cần có độ phức tạp thấp (tối ưu$log n$ hoặc $O(1)$ về thời gian).
Các cách tiếp cận
Cách Quy hoạch động (Dynamic Programming)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long countMod(long long l, long long r, int x) {
// Đếm số số trong [l, r] chia 3 dư x
// Công thức: floor((r - x) / 3) - floor((l - 1 - x) / 3)
return (r - x + 3) / 3 - (l - 1 - x + 3) / 3;
}
int main() {
long long n, l, r;
cin >> n >> l >> r;
// Đếm số lượng phần tử có giá trị chia 3 dư 0, 1, 2
long long cnt[3];
cnt[0] = countMod(l, r, 0);
cnt[1] = countMod(l, r, 1);
cnt[2] = countMod(l, r, 2);
// dp[i]: số cách tạo mảng sao cho tổng chia 3 dư i
long long dp[3] = {1, 0, 0};
for (int i = 0; i < n; i++) {
long long new_dp[3] = {0};
for (int j = 0; j < 3; j++) {
// Nếu thêm phần tử chia 3 dư 0, tổng dư j vẫn là j
new_dp[j] = (new_dp[j] + dp[j] * cnt[0]) % MOD;
// Nếu thêm phần tử chia 3 dư 1, tổng dư j trở thành (j+1)%3
new_dp[(j + 1) % 3] = (new_dp[(j + 1) % 3] + dp[j] * cnt[1]) % MOD;
// Nếu thêm phần tử chia 3 dư 2, tổng dư j trở thành (j+2)%3
new_dp[(j + 2) % 3] = (new_dp[(j + 2) % 3] + dp[j] * cnt[2]) % MOD;
}
for (int j = 0; j < 3; j++) dp[j] = new_dp[j];
}
cout << dp[0] << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Đây là cách tiếp cận trực tiếp nhất. Ta xác định số lượng các số trong khoảng [l, r] thuộc 3 nhóm: chia 3 dư 0, dư 1, dư 2. Gọi các số lượng này là cnt[0], cnt[1], cnt[2]. Sau đó, ta dùng mảng dp[i] để lưu số lượng cách tạo tổng chia 3 dư i sau khi đã chọn k phần tử. Với mỗi bước thêm 1 phần tử mới, ta cập nhật lại mảng dp. Công thức cập nhật: new_dp[(j + k) % 3] += dp[j] * cnt[k] (với k = 0, 1, 2). Độ phức tạp là O(n), chấp nhận được với n = 10^6.
Cách Ma trận chuyển trạng thái (Matrix Exponentiation)
#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
struct Matrix {
long long mat[3][3];
Matrix() {
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
mat[i][j] = 0;
}
Matrix operator*(const Matrix &other) const {
Matrix res;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
return res;
}
};
Matrix matrixPow(Matrix a, long long n) {
Matrix res;
for (int i = 0; i < 3; ++i) res.mat[i][i] = 1;
while (n > 0) {
if (n % 2 == 1) res = res * a;
a = a * a;
n /= 2;
}
return res;
}
long long countMod(long long l, long long r, int x) {
return (r - x + 3) / 3 - (l - 1 - x + 3) / 3;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n, l, r;
cin >> n >> l >> r;
long long c0 = countMod(l, r, 0);
long long c1 = countMod(l, r, 1);
long long c2 = countMod(l, r, 2);
// Xây dựng ma trận chuyển estado A
// Trạng thái: [Tổng dư 0, Tổng dư 1, Tổng dư 2]
// A[i][j]: số cách từ trạng thái j đến i sau 1 bước
// Từ j, thêm số dư 0 -> j
// Từ j, thêm số dư 1 -> (j+1)%3
// Từ j, thêm số dư 2 -> (j+2)%3
Matrix A;
A.mat[0][0] = c0; A.mat[1][0] = c1; A.mat[2][0] = c2;
A.mat[0][1] = c2; A.mat[1][1] = c0; A.mat[2][1] = c1;
A.mat[0][2] = c1; A.mat[1][2] = c2; A.mat[2][2] = c0;
// Ma trận khởi đầu: 1 cách để tổng dư 0, 0 cách cho các trường hợp khác
// Vector ban đầu [1, 0, 0]
// Kích thước n: A^n * [1, 0, 0]^T
Matrix res = matrixPow(A, n);
// Kết quả là phần tử đầu tiên của ma trận res (vì bắt đầu từ state 0)
cout << res.mat[0][0] << endl;
return 0;
}
- Time Complexity: O(log n)
- Space Complexity: O(1)
Phương pháp này tối ưu hơn về mặt thời gian. Bài toán có thể được mô hình hóa như một bài toán luyến thừa ma trận. Trạng thái là tổng hiện tại chia 3 dư bao nhiêu (0, 1, hoặc 2). Ma trận chuyển trạng thái A có kích thước 3x3, trong đó A[i][j] là số cách chuyển từ trạng thái j sang trạng thái i bằng 1 phần tử. Sau n bước, số cách sẽ là ma trận A^n. Do n có thể lên tới 10^6, ta dùng thuật toán lũy thừa nhanh (binary exponentiation) để tính A^n trong thời gian O(log n).
Cách Công thức tổ hợp (Combinatorial Formula)
#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
long long countMod(long long l, long long r, int x) {
return (r - x + 3) / 3 - (l - 1 - x + 3) / 3;
}
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2);
}
long long nCr_mod(long long n, long long r) {
if (r < 0 || r > n) return 0;
if (r == 0 || r == n) return 1;
if (r > n - r) r = n - r;
long long num = 1, den = 1;
for (int i = 0; i < r; i++) {
num = (num * (n - i)) % MOD;
den = (den * (i + 1)) % MOD;
}
return (num * modInverse(den)) % MOD;
}
int main() {
long long n, l, r;
cin >> n >> l >> r;
long long c0 = countMod(l, r, 0);
long long c1 = countMod(l, r, 1);
long long c2 = countMod(l, r, 2);
long long total = 0;
// Duyệt qua các trường hợp tổng chia hết cho 3
// Case 1: n chẵn, chọn n/2 số dư 1 và n/2 số dư 2
if (n % 2 == 0) {
long long k = n / 2;
long long ways = (nCr_mod(n, k) * nCr_mod(n - k, k)) % MOD;
total = (total + ways * power(c1, k) % MOD * power(c2, k)) % MOD;
}
// Case 2: tất cả đều là số chia hết cho 3
total = (total + power(c0, n)) % MOD;
// Case 3: n chia 3 dư 1, có 1 phần tử dư 1 và 2 phần tử dư 2 (tổng 1+4=5 chia 3 dư 2 -> sai)
// Để tổng chia hết cho 3, ta cần tổng các số dư 1 + 2*sl2 == 0 mod 3
// Hoặc tổng các số dư 2 + 2*sl1 == 0 mod 3
// Hoặc các cách khác.
// Phân tích:
// Tổng chia hết cho 3 <=> (sl1 + 2*sl2) % 3 == 0 (vì sl0 không ảnh hưưởng)
// Với sl1 + sl2 + sl0 = n.
// Ta có thể duyệt qua các khả năng của sl1 và sl2 sao cho (sl1 + 2*sl2) % 3 == 0.
// Do n <= 10^6, có thể dùng DP nhanh hơn là phân tích này.
// Tuy nhiên, nếu dùng công thức này, ta cần xử lý các trường hợp chia hết.
// Công thức Newton: (c0 + c1 + c2)^n = sum (n!/(a!b!c!)) * c0^a * c1^b * c2^c
// Điều kiện a + b + c = n và (b + 2c) % 3 == 0.
// Ta có thể dùng Chu kỳ tạo hàm (Generating Function).
// Đáp án là: 1/3 * ( (c0+c1+c2)^n + (c0 + c1*w + c2*w^2)^n + (c0 + c1*w^2 + c2*w)^n )
// Với w là căn nguyên hac bậc 3 của 1 (w = cis(2pi/3)).
// Tuy nhiên, w là số phức. Ta cần tính modulo 10^9+7.
// Trong field modulo, ta cần tìm phần tử w sao cho w^2 + w + 1 = 0 mod P.
// P = 10^9 + 7. P chia 3 dư 1 (10^9+7 = 3*333333335 + 2 -> Sai, 10^9+7 = 1000000007, 1000000007 % 3 = 2).
// Vì P chia 3 dư 2, nên phương trình x^2 + x + 1 = 0 không có nghiệm trong FP.
// Do đó, không thể dùng trực tiếp công thức generating function với số phức.
// Giải pháp thay thế: Dùng DP O(n) hoặc Ma trận O(log n) là tốt nhất.
// Hoặc có thể dùng Lucas Theorem nếu P chia 3 dư 1.
// Kết luận: Approaches 1 và 2 là chính xác. Approach 3 (Công thức tổ hợp tổng quát) phức tạp và không khả thi trong field này.
- Time Complexity: O(n) or O(log n)
- Space Complexity: O(1)
Approach này cố gắng tìm một công thức đóng kín. Tuy nhiên, đối với modulus $10^9+7$ (mà $10^9+7 \equiv 2 \pmod 3$), ta không thể đơn giản tách biệt các trường hợp bằng số phức. Một cách khác là dùng Quy Hoạch Động Optimize (DP Optimization) hoặc Chuỗi Sinh (Generating Functions) kết hợp Chứng minh lũy thừa (Exponentiation of Series), nhưng nó quá phức tạp cho bài này. Cách tiếp cận Ma trận (Solution 1) và DP (Solution 2) là tối ưu và khả thi nhất.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(1) | Quy hoạch động (Dynamic Programming) |
| 2 | O(log n) | O(1) | Ma trận chuyển trạng thái (Matrix Exponentiation) |
| 3 | O(n) or O(log n) | O(1) | Công thức tổ hợp (Combinatorial Formula) |
Bài học kinh nghiệm
- Bài toán quy về đếm số cách chọn $n$ phần tử sao cho tổng của chúng chia hết cho 3.
- Chỉ quan tâm đến giá trị các phần tử chia 3 dư bao nhiêu (0, 1, 2).
- Số cách có thể tính bằng phương pháp quy hoạch động (DP) với độ phức tạp $O(n)$ hoặc ma trận chuyển trạng thái với độ phức tạp $O(\log n)$.
Lỗi thường gặp
- Sai công thức tính số lượng số nguyên trong đoạn [l, r] chia 3 dư x. Cần chú ý đến trường hợp l và r âm (mặc dù đề bài cho $l \ge 1$) và cách làm tròn số nguyên.
- Quên kiểm tra số dư modulo $10^9+7$ trong các phép tính nhân và cộng, đặc biệt khi n lớn.
- Lạm dụng công thức tổng quát (Generating Functions) với số phức mà không kiểm tra tính tồn tại của căn nguyên hac bậc 3 trong field số nguyên modulo hiện tại.
Bình luận