Tìm xn
Đề bài
Cho dãy số $x_n$ được định nghĩa như sau:
- $x_0 = 1$
- $x_1 = 2$
- $x_n = n \cdot x_0 + (n - 1) \cdot x_1$ $+ (n - 2) \cdot x_2$ $+ \ldots + 1 \cdot x_{n-1}$
Hãy in ra kết quả $x_n \bmod (10^9 + 7)$.
Input
- Dòng đầu tiên là số $T$ là số lượng bộ test ($T \le 10^6$).
- $T$ dòng tiếp theo, mỗi dòng có 1 số $n$ ($0 \le n \le 10^7$).
Output: in ra $T$ dòng, mỗi dòng là giá trị $x_n \bmod (10^9 + 7)$.
Subtask
- 30% số test đầu tiên có $T \le 10$, $n \le 10^3$.
- 20% số test tiếp theo có $T \le 10^6$, $n \le 10^3$.
- 30% số test tiếp theo có $T \le 10$, $n \le 10^7$.
- 20% số test còn lại không có giới hạn gì thêm.
4
0
1
4
61
2
29
199Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
30%Subtask 1: tính thẳng theo định nghĩa – O(T × N²)
Bài này nhìn thoáng qua ta thấy nếu dùng mảng 1 chiều xử lý thì sẽ rất gọn, theo đúng quy tắc đề đã đưa ra thôi. Ta gán sẵn a[0] = 1, a[1] = 2, rồi giả sử cần tính $n = 6$ thì bắt đầu tiếp từ $i = 2$ đến $i = 6$, mỗi lần sẽ đi tính toàn bộ các thằng trước đó:
a[3] = 3*a[0] + 2*a[1] + 1*a[2]
a[4] = 4*a[0] + 3*a[1] + 2*a[2] + 1*a[3]
…
Cứ thế tính cho đến $n$ thôi. Nhớ trong quá trình tính liên tục chia dư để tránh bị tràn số. Thì cách làm đơn giản nhất là dùng 2 vòng lặp lồng nhau thôi:
Xem code subtask 1
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long m = 1e9 + 7;
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<long long> a(n + 1, 0);
a[0] = 1;
if(n >= 1){
a[1] = 2;
}
for(int i = 2; i <= n; ++i){
long long cnt = i;
for(int j = 0; j < i; ++j){
a[i] += cnt * a[j];
cnt--;
a[i] %= m;
}
}
cout << a[n] << '\n';
}
return 0;
}import sys
input = sys.stdin.readline
m = int(1e9 + 7)
t = int(input())
for _ in range(t):
n = int(input())
a = [0] * (n + 1)
a[0] = 1
if n >= 1:
a[1] = 2
for i in range(2, n + 1):
cnt = i
for j in range(i):
a[i] = (a[i] + cnt * a[j]) % m
cnt -= 1
print(a[n])vector a(n + 1), nên khi $n = 0$ mảng chỉ có 1 phần tử a[0]; nếu vẫn gán a[1] = 2 thì sẽ ghi ra ngoài mảng (lỗi truy cập bộ nhớ, có thể chạy vẫn ra đúng nhưng cũng có thể crash tuỳ máy). Mà test ví dụ có luôn $n = 0$. Vì vậy trong code trên mình thêm điều kiện if(n >= 1) trước khi gán a[1] = 2, giống y như bản Python.Độ phức tạp: $O(T \times N^2)$. Thì code trên sẽ chỉ lấy được Subtask 1 với 30% điểm đầu tiên khi $T \le 10$, $N \le 10^3$, bởi $T \times N^2 = 10^7$ thì thỏa $\le 10^8$ chạy trong 1 giây (với C++). Tuy nhiên với Subtask 2: $T \le 10^6$ và $N \le 10^3$ thì $T \times N^2 = 10^6 \times 10^6 = 10^{12}$, thì đã vượt quá giới hạn $10^8$ (1 giây của C++) nên chắc chắn TLE.
+20%Subtask 2: tính trước 1 lần cho mọi n ≤ 1000
Với Subtask 2: $T \le 10^6$, $N \le 10^3$. Ta nhận thấy rằng giá trị $N$ khá nhỏ (tối đa chỉ là 1000), trong khi đó có quá nhiều test (lên tới 1 triệu). Vì vậy ta có thể tận dụng lại code của Subtask 1 ở trên nhưng tính trước kết quả cho tối đa $N = 1000$ lưu trữ lại trong mảng kết quả, từ đó với mỗi truy vấn sẽ gọi vào trong mảng kết quả in ra thôi.
Xem code subtask 2
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long m = 1e9 + 7;
int maxN = 1000;
vector<long long> a(maxN + 1, 0);
a[0] = 1;
a[1] = 2;
for(int i = 2; i <= maxN; ++i){
long long cnt = i;
for(int j = 0; j < i; ++j){
a[i] += cnt * a[j];
cnt--;
a[i] %= m;
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << a[n] << '\n';
}
return 0;
}import sys
input = sys.stdin.readline
m = int(1e9 + 7)
maxN = 1000
a = [0] * (maxN + 1)
a[0] = 1
a[1] = 2
for i in range(2, maxN + 1):
cnt = i
for j in range(i):
a[i] = (a[i] + cnt * a[j]) % m
cnt -= 1
t = int(input())
for _ in range(t):
n = int(input())
print(a[n])Độ phức tạp: $O(maxN^2 + T)$, thì $maxN$ tối đa 1000 nên $maxN^2$ = 1 triệu, và $T$ tối đa cũng là 1 triệu nên tổng là 2 triệu và hoàn toàn yên tâm chạy trong 1 giây. Code này sẽ lấy được Subtask 1 & 2 với 50% điểm. Còn Subtask 3 khi $T$ tối đa 10 và $N$ tối đa $10^7$ thì sẽ thua, bởi vì $maxN$ tối đa $10^7$ thì $maxN^2 = 10^{14}$, đã vượt quá ngưỡng $10^8$ rồi nên chắc chắn sẽ bị TLE.
100%Subtask 3 & 4: tìm ra quy luật, mỗi số chỉ tốn O(1)
Subtask 3: $T$ tối đa 10, $N$ tối đa $10^7$. Subtask 4: $T$ tối đa $10^6$, $N$ tối đa $10^7$. Lúc này chắc chắn ta cần tìm ra cách tính a[n] với độ phức tạp tốt hơn, không thể dùng 2 vòng lặp lồng nhau như hiện tại bởi độ phức tạp quá cao. Để làm được điều đó ta sẽ phân tích 1 chút:
| n | Khai triển | Giá trị |
|---|---|---|
| x2 | 2·1 + 1·2 | 4 |
| x3 | 3·1 + 2·2 + 1·4 | 11 |
| x4 | 4·1 + 3·2 + 2·4 + 1·11 | 29 |
| x5 | 5·1 + 4·2 + 3·4 + 2·11 + 1·29 | 76 |
| x6 | 6·1 + 5·2 + 4·4 + 3·11 + 2·29 + 1·76 | 199 |
Nếu các bạn ghi ra dãy kết quả theo 1 hàng ngang đi, sẽ dễ nhìn thấy quy luật của nó:
Các bạn nhìn kỹ hen: số 4 (a[2]) là mình chủ động tính ra, nhưng khi đã có nó rồi thì các bạn nhìn nhé, về sau nó có 1 quy tắc. Ví dụ tính a[3] đi hen: nó sẽ là tổng của các thằng trước đó (a[0] + a[1] + a[2]) và cộng thêm 1 lần a[2] nữa, tức là sẽ là $1 + 2 + 4 + 4 = 11$. Tương tự vậy, tính a[4] hen: nó sẽ là tổng của các thằng trước đó (a[0] + a[1] + a[2] + a[3]) và cộng thêm 1 lần a[3] nữa, tức là $1 + 2 + 4 + 11 + 11 = 29$. Cứ thế …
sum thì chỉ cần duyệt 1 lần, tức là độ phức tạp $O(n)$ để tính ra kết quả.Ví dụ trong trường hợp tính a[3], ta có tổng các số từ a[0] đến a[1] là 3 rồi, cộng thêm 2 lần a[2] là 8 nữa thì thành 11. Rồi giờ muốn tính a[4] thì lấy tổng các số từ a[0] đến a[2] mà ta đã lưu trữ là 7, giờ chỉ là cộng thêm 2 lần của a[3], tức là $2 \times 11 = 22$, và $7 + 22 = 29$. Và lúc này nhớ cập nhật tổng các số từ a[0] đến a[3] = 7 + 11 = 18, để khi tính a[5] sẽ gọi tổng đã lưu là 18, rồi cộng với 2 lần a[4], tức là $18 + 2 \times 29 = 76$. Đó, các bạn nhìn ra quy luật này của dãy số hen:
| Tính | sum (đã lưu) | + 2 lần số liền trước | Kết quả | Cập nhật sum |
|---|---|---|---|---|
| a[3] | a[0] + … + a[1] = 3 | 2 × a[2] = 2 × 4 = 8 | 11 | sum = 3 + 4 = 7 |
| a[4] | a[0] + … + a[2] = 7 | 2 × a[3] = 2 × 11 = 22 | 29 | sum = 7 + 11 = 18 |
| a[5] | a[0] + … + a[3] = 18 | 2 × a[4] = 2 × 29 = 58 | 76 | sum = 18 + 29 = 47 |
| a[6] | a[0] + … + a[4] = 47 | 2 × a[5] = 2 × 76 = 152 | 199 | sum = 47 + 76 = 123 |
Em nhập $n$ rồi bấm Tiếp để so sánh cách tính theo định nghĩa (cộng cả dãy) với quy luật sum + 2 * a[i - 1]:
Vì sao lại có quy luật này? (chứng minh nhanh)
Viết $x_n$ và $x_{n-1}$ theo định nghĩa rồi trừ cho nhau:
x[n−1] = (n−1)·x[0] + (n−2)·x[1] + … + 1·x[n−2]
Mỗi hệ số chênh nhau đúng 1, nên $x_n - x_{n-1} = x_0 + x_1 + \ldots + x_{n-1}$, tức là $x_n = (x_0 + \ldots + x_{n-2}) + 2x_{n-1}$, đúng như quy luật ở trên. Riêng $x_2$ không theo quy luật này vì $x_1 = 2$ là giá trị đề cho sẵn chứ không tính theo công thức (theo công thức thì $x_1$ phải là $1 \cdot x_0 = 1$), nên ta phải tự tính $x_2 = 4$ trước rồi mới bắt đầu áp dụng quy luật từ $x_3$.
Thú vị hơn nữa: từ $x_4$ trở đi còn có thể viết gọn thành $x_n = 3x_{n-1} - x_{n-2}$ (ví dụ $3 \times 11 - 4 = 29$, $3 \times 29 - 11 = 76$), và các số 4, 11, 29, 76, 199, … chính là các số Lucas ở vị trí lẻ. Bạn nào thích toán có thể tìm hiểu thêm.
Và ta có 1 đoạn code sau đây để giải quyết full điểm cho toàn bộ các Subtask. Đó là ta thấy $N$ tối đa $10^7$ thì ta sẽ đi tính trước toàn bộ $10^7$ trường hợp lưu vào mảng kết quả, và nhớ là tính theo cách dùng 1 vòng lặp xét qua thôi với độ phức tạp $O(maxN)$. Sau đó với mỗi bộ test ta gọi vào mảng kết quả lấy giá trị in ra, nên độ phức tạp bước sau đó nữa là $O(T)$. Vậy tổng lại độ phức tạp sẽ là $O(maxN + T)$, thì $maxN$ tối đa $10^7$, $T$ tối đa $10^6$ thì tổng lại chỉ là 11 triệu, hoàn toàn chạy được trong 1 giây (với C++ vì ngưỡng 1 giây của C++ là $10^8$).
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n = 1e7;
long long m = 1e9 + 7;
vector<long long> a(n + 1);
a[0] = 1;
a[1] = 2;
a[2] = 4;
long long sum = a[0] + a[1];
for(int i = 3; i <= n; ++i){
a[i] = sum + 2 * a[i - 1];
sum += a[i - 1];
a[i] %= m;
sum %= m;
}
int t, x;
cin >> t;
while(t--){
cin >> x;
cout << a[x] << '\n';
}
return 0;
}import sys
input = sys.stdin.readline
n = int(1e7)
m = int(1e9 + 7)
a = [0] * (n + 1)
a[0] = 1
a[1] = 2
a[2] = 4
sum_ = a[0] + a[1]
for i in range(3, n + 1):
a[i] = (sum_ + 2 * a[i - 1]) % m
sum_ = (sum_ + a[i - 1]) % m
t = int(input())
for _ in range(t):
x = int(input())
print(a[x])Mình chạy thử với $T = 10^6$ truy vấn: bản C++ mất khoảng 0.34 giây. Mảng vector<long long> $10^7$ phần tử tốn khoảng 80 MB; nếu hệ thống chấm giới hạn bộ nhớ chặt thì có thể đổi sang vector<int> (vì giá trị sau khi chia dư luôn nhỏ hơn $10^9 + 7$, vẫn vừa kiểu int) để chỉ còn khoảng 40 MB. Bản Python cùng ý tưởng mất khoảng 5 giây vì phải lặp $10^7$ lần, nên với subtask lớn các bạn nên nộp bản C++ nhé.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét