Bảng đẹp
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019
Bình luận
Subtask 1
Ta duyệt qua mỗi bộ chỉ số \((x,y,u,v)\), tượng trưng cho một hình chữ nhật con trong \(O((m\times n)^2)\). Với mỗi HCN con, ta lại duyệt mọi \((i,j)\) mà \(x \le i \le u\) và \(y \le j \le v\) để tính tổng. Độ phức tạp \(O((m\times n)^3)\)
Subtask 2
Vẫn duyệt qua mỗi bộ chỉ số \((x,y,u,v)\) trong \(O((m\times n)^2)\). Tổng một bảng con có thể lấy trong \(O(1)\) bằng tổng tiền tố hai chiều.
Độ phức tạp \(O((m\times n)^2)\)
Subtask 3
Ta duyệt qua các cặp chỉ số \((x,u)\). Với mỗi \((x,u)\), ta cần đếm tất cả bộ \((y,v)\) thỏa mãn \((x,y,u,v)\) là một bảng đẹp trong ĐPT \(O(n)\) hoặc tốt hơn.
Với mỗi \(i : 1 \le i \le n\), đặt \(b(i) = \sum a_{r,i}\) với \(r\) chạy từ \(x\) tới \(u\). Bài toán đưa về : Đếm số đoạn con \([l,r]\) trong \(b\) có tổng chia hết cho 9. Ta giải bài toán này trong \(O(n)\). Độ phức tạp tổng quát \(O(m^2 \times n)\)