Hình vuông (THT TP 2020)
Xem PDFCho một lưới hình vuông chứa rất nhiều ô vuông nhỏ. Mỗi ô vuông trong lưới hình vuông này được xác định vị trí bởi một cặp số \((i,j)\), trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột. Các hàng được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1,2,3,...\) kể từ trên xuống dưới; các cột được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1,2,3,...\) kể từ trái sang phải. Các ô vuông trong lưới hình vuông được ghi một số tự nhiên bằng tích của chỉ số hàng và chỉ số cột của ô vuông đó.
Chọn ra hình vuông chứa \(K \times K\) ô vuông trong lưới hình vuông đã cho. Gọi \(T\) là tổng các số trong các ô vuông có trong hình vuông đã chọn.
Yêu cầu: Hãy tìm số dư trong phép chia \(T : 20192020\).
Ví dụ: Cho lưới hình vuông, ta chọn một hình vuông gồm \(3 \times 3\) ô vuông, trong đó ô vuông ở góc bên trái có chỉ số hàng bằng \(2\) và chỉ số cột bằng \(1\) (hình mình họa).
Input
- Một dòng duy nhất chứa 3 số nguyên \(i,j,K(1 \leq i \leq 1000;1 \leq j \leq 1000;1 \leq K \leq 10 ^ 8)\). Trong đó \(i\) và \(j\) lần lượt là chỉ số hàng và chỉ số cột của ô vuông ở góc bên trái của hình vuông được chọn; \(K\) là số ô vuông trên một hàng (và là số ô vuông trên một cột) của hình vuông được chọn.
Output
- Số dư của phép chia \(T : 20192020\).
Example
Test 1
Input
2 1 3 Output
54
Bình luận
đề hảo hán quá :))) yêu cầu trên đề là mod kq cho 20192020 mà output bên dưới lại ghi kq mod 20192022
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
\(\implies x+(x+1)+...+x+q-1=F(x+q-1)-F(x-1)\)
Gọi \(S\) là kết quả của bài toán cần tìm, khi đó ta có:
\(S=\sum\limits_{u=i}^{i+k-1}\sum\limits_{v=j}^{j+k-1}u*v=\sum\limits_{u=i}^{i+k-1} u*(j+(j+1)+...+(j+k-1))\)
\(=\sum\limits_{u=i}^{i+k-1} u*[F(j+k-1)-F(j-1)]=[F(j+k-1)-F(j-1)](i+(i+1)+...+(i+k-1))\)
\(=[F(i+k-1)-F(i-1)][F(j+k-1)-F(j-1)]\)
Khi đó ta có: \(S\text{ % }mod = [(G(i+k-1)-G(i-1)+mod)\text{ % }mod][(G(j+k-1)-G(j-1)+mod)\text{ % }mod]\text{ % }mod\)
Như vậy bài toán đã được giải quyết xong.
Các bạn có thể tham khảo code tại \(\href{https://ideone.com/qGcOxL}{đây}\)
Vào bomto/20192020 ấy
đề mô ?
.
Công thứccccc ;))