Ma trận xoắn ốc 2
Đề bài
Khi học về ma trận (mảng 2 chiều có $M$ hàng, $N$ cột), thầy sẽ ra cho các bạn 1 bài về ma trận xoắn ốc. Ma trận xoắn ốc là một ma trận vuông có $M = N$, được sinh ra khi biết kích thước $N$. Với số 1 ở trung tâm ma trận, di chuyển theo hình xoắn ốc ngược chiều kim đồng hồ, rồi lần lượt điền các số tăng dần 1, 2, 3, 4, 5 …
Một số ví dụ về ma trận xoắn ốc:
| 4 | 3 |
| 1 | 2 |
| 5 | 4 | 3 |
| 6 | 1 | 2 |
| 7 | 8 | 9 |
| 16 | 15 | 14 | 13 |
| 5 | 4 | 3 | 12 |
| 6 | 1 | 2 | 11 |
| 7 | 8 | 9 | 10 |
| 17 | 16 | 15 | 14 | 13 |
| 18 | 5 | 4 | 3 | 12 |
| 19 | 6 | 1 | 2 | 11 |
| 20 | 7 | 8 | 9 | 10 |
| 21 | 22 | 23 | 24 | 25 |
Việc sinh ra ma trận xoắn ốc trở nên nhàm chán, thầy quyết định các bạn không cần phải sinh ra ma trận này làm gì. Thầy chỉ muốn biết tổng của các số trên 2 đường chéo chính của ma trận xoắn ốc là bao nhiêu. Ví dụ:
| N | Tổng các số trên 2 đường chéo |
|---|---|
| 2 | 1 + 3 + 2 + 4 = 10 |
| 3 | 5 + 1 + 9 + 7 + 3 = 25 |
| 4 | 16 + 4 + 2 + 10 + 13 + 3 + 1 + 7 = 56 |
| 5 | 17 + 5 + 1 + 9 + 25 + 21 + 7 + 3 + 13 = 101 |
Vì tổng này quá lớn, các kiểu dữ liệu cơ bản không thể chứa được, thầy chỉ cần các bạn tính được tổng này mod $(10^9 + 9)$ là được.
Input
- Dòng 1: số $T$ là số test case ($1 \le T \le 10^5$).
- Dòng 2 đến $T + 1$: chứa số $N$ ($1 \le N \le 10^7$).
Output: gồm $T$ dòng, dòng thứ $i$ chứa kết quả tương ứng với test case thứ $i$.
Subtask
- 20% số test đầu tiên có $T \le 10$, $N \le 1000$.
- 20% số test tiếp theo có $T \le 10^3$, $N \le 8000$.
- 60% số test còn lại không có giới hạn gì thêm.
5
2
3
4
5
1000000010
25
56
101
679604006Lờ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 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesBài này cách vét cạn có thể lấy được 40% điểm khi mà tạo ra cái ma trận xoắn ốc theo quy luật đề mô tả, không khó để làm được. Bây giờ anh sẽ tập trung vào cách làm tối ưu để full 100% điểm nhé.
Nháp ra giấy và tìm quy luật
Lời khuyên là em hãy nháp ra giấy vẽ hình ma trận xoắn ốc với các trường hợp $N$ từ 2 đến 6 thôi là được rồi; với mỗi trường hợp em ghi ra dãy các số nằm trên 2 đường chéo chính và chéo phụ (các ô màu cam bên dưới) và hãy ghi nó theo thứ tự giá trị tăng dần:
| 4 | 3 |
| 1 | 2 |
| 5 | 4 | 3 |
| 6 | 1 | 2 |
| 7 | 8 | 9 |
| 16 | 15 | 14 | 13 |
| 5 | 4 | 3 | 12 |
| 6 | 1 | 2 | 11 |
| 7 | 8 | 9 | 10 |
| 17 | 16 | 15 | 14 | 13 |
| 18 | 5 | 4 | 3 | 12 |
| 19 | 6 | 1 | 2 | 11 |
| 20 | 7 | 8 | 9 | 10 |
| 21 | 22 | 23 | 24 | 25 |
Em sẽ nhìn ra quy luật như sau (số màu xanh là 4 số mới thêm vào so với trường hợp $N - 2$):
| N | Dãy số trên 2 đường chéo (tăng dần) | Tổng |
|---|---|---|
| 2 | 1 2 3 4 | 10 |
| 3 | 1 3 5 7 9 | 25 |
| 4 | 1 2 3 4 7 10 13 16 | 56 |
| 5 | 1 3 5 7 9 13 17 21 25 | 101 |
| 6 | 1 2 3 4 7 10 13 16 21 26 31 36 | 170 |
Nhìn kỹ em sẽ thấy rõ quy luật của nó, nếu vẫn chưa thấy được thì xem tiếp anh sẽ chỉ ra cho em thấy rõ. Hãy chú ý đến 2 trường hợp khởi đầu: trường hợp $N$ chẵn ($N = 2$) và trường hợp $N$ lẻ ($N = 3$). Từ 2 dãy này ta sẽ có các quy luật cho các trường hợp tiếp theo như sau:
- Trường hợp $N = 4$ sẽ là dãy các số của trường hợp $N = 2$ và thêm 4 giá trị mới.
- Trường hợp $N = 5$ sẽ là dãy các số của trường hợp $N = 3$ và thêm 4 giá trị mới.
- Trường hợp $N = 7$ sẽ là dãy các số của trường hợp $N = 5$ và thêm 4 giá trị mới.
Vậy nghĩa là ta cần có được dãy số của trường hợp trước đó của nó (phân rõ theo chẵn/lẻ: nếu trường hợp hiện tại $N$ đang là lẻ thì nghĩa là xét trường hợp $N$ lẻ gần nhất trước đó, và dãy hiện tại sẽ bằng dãy trước đó với thêm 4 số mới; tương tự như vậy với trường hợp $N$ chẵn).
Tìm 4 số mới
Vấn đề 4 số mới của trường hợp $N$ hiện tại cần tìm ra nó bằng quy luật thế nào? Để ý em sẽ thấy quy luật như sau: ví dụ khi $N = 2$ thì dãy là 1 2 3 4. Vậy khi $N = 4$ là trường hợp chẵn tiếp theo thì số cuối cùng trong 4 số sẽ là $N^2$ $= 4^2 = 16$. Khi đã xác định được số cuối cùng trong 4 số thì việc tìm ra 3 số đứng trước nó khá đơn giản, lúc này chỉ là lần lượt lấy giá trị số cuối cùng tìm được trừ đi cho $(N - 1)$ liên tiếp 3 lần là ra.
16 − 3 = 13
13 − 3 = 10
10 − 3 = 7
25 − 4 = 21
21 − 4 = 17
17 − 4 = 13
Hoặc đơn giản nhất ta lấy số cuối cùng của trường hợp $N$ trước đó liên tục cộng dồn thêm 4 lần của $(N - 1)$. Ví dụ số cuối cùng của trường hợp $N = 2$ là số 4, vậy 4 số tiếp theo sẽ là: 4 + 3 = 7, 7 + 3 = 10, 10 + 3 = 13, 13 + 3 = 16.
Giờ đây khi đã nhìn ra quy luật tạo dãy số này rồi thì em thử suy nghĩ xem cần phải code thế nào cho dễ dàng đơn giản nhất mà hiệu suất chạy tối ưu, không bị quá thời gian với độ lớn dữ liệu đề bài đưa ra. Lúc này đây cũng sẽ phải tư duy suy nghĩ thêm nhiều đấy nhé 😉, thử sức xem, nếu không được thì xem tiếp phần dưới anh sẽ nói nốt luôn.
Em nhập $N$ rồi bấm Tiếp để xem ma trận lớn dần từ trong ra ngoài, mỗi lần N tăng 2 thì chỉ có thêm đúng 4 số ở 4 góc:
Tính trước toàn bộ kết quả
Với những phân tích ở trên thì thấy rằng để tính được giá trị của trường hợp $N$ cần tính được trước đó trường hợp $N - 2$: tính tổng dãy số của trường hợp $N - 2$ rồi lấy kết quả tổng đó cộng thêm tổng của 4 số mới của trường hợp $N$ hiện tại là ra kết quả hiện tại cần tìm của trường hợp $N$:
Vậy nhìn thấy nếu theo công thức này để tính được trường hợp $N$ hiện tại thì cần tính được các trường hợp $N - 2$, $N - 4$, $N - 6$ … trước đó. Như thế nếu với $T$ bộ test, cứ với mỗi trường hợp $N$ ta lại đi tính từ đầu đến $N$ và lặp đi lặp lại quy trình này $T$ lần, thì như vậy đó sẽ không phải cách làm tốt vì cứ bị tính đi tính lại nhiều lần không cần thiết, và có thể dẫn đến thuật toán bị chạy quá giới hạn thời gian cho phép. Ví dụ đầu tiên $N = 10$ thì ta tính qua các trường hợp $N = 2, 4, 6, 8$ rồi mới có kết quả tính ra $N = 10$. Nhưng tiếp đó lại có yêu cầu tính $N = 8$ thì lúc này đây ta lại đi tính các trường hợp $N = 2, 4, 6$, và em có thấy rõ ràng những trường hợp này mình đã tính trước đó ở trường hợp $N = 10$ rồi không? Nên làm như thế này sẽ không tốt.
Giải pháp xử lý tốt hơn đó là với phạm vi dữ liệu đề bài cho, trường hợp $N$ lớn nhất là $10^7$. Như thế ta sẽ đi tính hết tất cả kết quả các trường hợp $N$ từ 2 đến $10^7$ và lưu trữ các kết quả đó vào trong mảng đáp án tại vị trí index tương ứng, ví dụ res[N] là đáp án của trường hợp $N$. Tạo ra được mảng res lưu trữ hết tất cả các tình huống như thế thì với mỗi bộ test với giá trị $N$ đọc vào chỉ cần gọi res[N] là lấy ra ngay lập tức đáp án chỉ trong $O(1)$ phép tính. Thực tế ta không cần tính đủ $10^7$ trường hợp vì đây chỉ là tình huống xấu nhất, chỉ cần tìm ra Max (số lớn nhất) trong các trường hợp dữ liệu đầu vào rồi tính đến Max là được.
(a − b) % c = ((a % c) − (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c
Vậy nên nếu áp dụng theo tư tưởng giải thuật này thì độ phức tạp bước tạo ra mảng res là $O(\max N)$ với trường hợp lớn nhất $N = 10^7$. Sau đó $O(T)$ để xử lý $T$ bộ test, với trường hợp lớn nhất $T = 10^5$; còn với mỗi bộ test thì chỉ mất $O(1)$ để in ra res[N]. Vậy tổng quát độ phức tạp là $O(\max N + T)$. Trường hợp xấu nhất là khi $T = 10^5$, $N = 10^7$, lúc này sẽ là $O(10^7 + 10^5)$ và vẫn không lo bị TLE, vì nguyên tắc để không bị TLE thì số phép toán tối đa thực hiện trong ngưỡng $(3 \div 5) \times 10^7$, và với giới hạn này vẫn chưa bị vượt qua nên thuật toán này đảm bảo ổn.
Đây là code xử lý theo tư tưởng anh đã nói ở trên cho em tham khảo:
#include <bits/stdc++.h>
using namespace std;
const long long M = 1000000009;
const int MAX = 1e7;
long long res[MAX + 10];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
res[1] = 1; // 1
res[2] = 10; // 1 2 3 4
res[3] = 25; // 1 3 5 7 9
// vì tính i*i nên chắc ăn biến i nên là kiểu long long để không bị tràn dữ liệu
for(long long i = 4; i <= MAX; i++){
long long num1 = i * i;
long long num2 = num1 - (i - 1);
long long num3 = num2 - (i - 1);
long long num4 = num3 - (i - 1);
res[i] = (res[i - 2] + (num1 % M) + (num2 % M) + (num3 % M) + num4 % M) % M;
}
int t, x;
cin >> t;
while(t--){
cin >> x;
cout << res[x] << '\n';
}
return 0;
}M = 1000000009
MAX = 10**7
res = [0] * (MAX + 10)
res[1] = 1 # 1
res[2] = 10 # 1 2 3 4
res[3] = 25 # 1 3 5 7 9
for i in range(4, MAX + 1):
num1 = i * i
num2 = num1 - (i - 1)
num3 = num2 - (i - 1)
num4 = num3 - (i - 1)
res[i] = (res[i - 2] + (num1 % M) + (num2 % M) + (num3 % M) + (num4 % M)) % M
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
x = int(input())
print(res[x])Mình chạy thử với $T = 10^5$: bản C++ mất khoảng 0.1 giây. Bản Python thì phải tạo list $10^7$ phần tử và lặp $10^7$ lần nên mất khoảng 7.5 giây và tốn rất nhiều bộ nhớ; bạn nào code Python thì xem phần đọc thêm ngay dưới đây nhé.
O(1)Đọc thêm: công thức tính thẳng cho N bất kỳ
Lúc viết bài anh có nói "có thể sẽ có cách làm tốt hơn đi tính trực tiếp ra kết quả của trường hợp $N$ bất kỳ chỉ trong $O(1)$ bằng cách xác định đúng công thức toán học". Thì thực ra là có thật nha các em 😜. Cộng 4 số mới lại ta được $4N^2 - 6(N - 1)$, tức là mỗi bước cộng thêm $4N^2 - 6N + 6$. Cộng dồn các bước đó (dùng công thức tổng các bình phương) sẽ ra:
Thử lại: $N = 3$: $(108 + 27 + 24 - 9) / 6 = 25$ ✓; $N = 4$: $(256 + 48 + 32) / 6 = 56$ ✓; $N = 5$: $(500 + 75 + 40 - 9) / 6 = 101$ ✓. Mình cũng đã so kết quả của công thức với code ở trên trên $10^5$ test ngẫu nhiên (kể cả $N = 10^7$), kết quả khớp hoàn toàn.
Chỉ có 1 chỗ cần cẩn thận: với $N = 10^7$ thì $4N^3$ lên tới $4 \times 10^{21}$, vượt kiểu long long, nên trong C++ ta phải tính tử số theo modulo rồi nhân với nghịch đảo modulo của 6 (vì $10^9 + 9$ là số nguyên tố nên nghịch đảo của 6 là $6^{10^9+7} \bmod (10^9+9)$, tính bằng lũy thừa nhanh). Còn Python thì số nguyên không giới hạn nên tính thẳng luôn:
Xem code công thức O(1)
#include <bits/stdc++.h>
using namespace std;
const long long M = 1000000009;
long long power(long long a, long long b){ // a^b % M
long long res = 1;
a %= M;
while(b > 0){
if(b & 1){
res = res * a % M;
}
a = a * a % M;
b >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long inv6 = power(6, M - 2); // nghịch đảo modulo của 6
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
long long x = n % M;
long long tu = (4 * (x * x % M) % M * x % M + 3 * (x * x % M) % M + 8 * x) % M;
if(n % 2 == 1){
tu = (tu - 9 + M) % M; // N lẻ thì trừ thêm 9
}
cout << tu * inv6 % M << '\n';
}
return 0;
}import sys
def main():
M = 1000000009
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(1, t + 1):
n = int(data[i])
if n % 2 == 1:
s = (4 * n**3 + 3 * n**2 + 8 * n - 9) // 6
else:
s = (4 * n**3 + 3 * n**2 + 8 * n) // 6
out.append(s % M)
print("\n".join(map(str, out)))
main()