[Số học] [Tô màu bàn cờ] [Number Theory] [Chessboard Coloring] [AtCoder] AGC027-D Modulo Matrix

Đề bài

Tóm tắt đề bài

Tạo bảng kích thước n*n sao cho các số trong bảng đôi một khác nhau và với mọi hai số (x,y) kề cạnh, ta có max(x,y)%min(x,y) = m với m là hai số nguyên dương nào đó. Ngoài ra, các số trong bảng không được vượt quá 10^15.

Ý tưởng

Tô màu kiểu bàn cờ cho bảng, sau đó điền hết ô đen với các số bất kì, khi đó số ở ô trắng sẽ bằng bội chung lớn nhất của các ô đen kề với nó + 1.

Lời giải

Để đảm bảo các số trong bảng đôi một khác nhau, với mỗi đường chéo đen chính và đường chéo đen phụ, ta gán với đường chéo đó một số nguyên tố khác nhau. Mỗi ô đen sẽ có giá trị bằng tích của hai số nguyên tố được gán với hai đường chéo đi qua ô đó. Khi đó, số ở ô trắng sẽ bằng tích của bốn số nguyên tố nguyên tố của bốn đường chéo đen giáp với nó cộng 1. Dễ dàng nhận thấy rằng số ở các ô là khác nhau.

(Lưu ý ta gán số nguyên tố cho cả những đường chéo nằm ngoài bảng để đảm bảo các ô trắng ở mép không bị trùng nhau)

Ta thấy trong trường hợp xấu nhất (n = 500), ta chỉ có khoảng 1000 đường chéo đen. Do số nguyên tố thứ 1000 bằng 7919, ta thấy chỉ cần gán số nguyên tố sao cho các đường chéo chính có số nguyên tố nhỏ sẽ giáp với các đường chéo phụ có số nguyên tố lớn là hoàn toàn có thể thỏa mãn được điều kiện các số trong bảng không vượt quá 10^15.

Code (Java)

[Quy hoạch động] [Tổ hợp] [Bao hàm - Loại trừ] [Đường tròn] [Dynamic Programming] [Combinatorics] [Inclusion-Exclusion] [Circle] [AtCoder] AGC028-D Chords

Đề bài

Tóm tắt đề bài

Cho 2N điểm cách đều nhau trên đường tròn và K cặp điểm được nối sẵn, tính tổng của tổng số thành phần liên thông của các cách nối N-K cặp điểm còn lại.

Ý tưởng

Đếm số lần xuất hiện của các thành phần liên thông có i là điểm có chỉ số nhỏ nhất và j là điểm có chỉ số lớn nhất, ta gọi thành phần liên thông như vậy là thành phần (i,j).

Lời giải

Ta có thể sử dụng phương pháp quy hoạch động để tính số loại thành phần (i,j).

Đầu tiên, gọi x là số điểm chưa được nối trong số các điểm có chỉ số từ i đến j, ta thấy số cách nối các điểm này là (x-1)*(x-3)*...*1 (nếu x chẵn, nếu x lẻ thì ta không có cách nối). Tuy nhiên, ta thấy rằng không phải bất cứ cách nối nào cũng cho ta đúng một loại thành phần (i,j) (vì có thể có trường hợp nối thành hai thành phần (i,k) và (k,j) với k nằm giữa i và j). Do đó, ta phải tìm cách loại các trường hợp này ra.

Sau một hồi suy nghĩ, gọi dp(i,j) là số loại thành phần (i,j), ta có công thức quy hoạch động
dp(i,j) = (số cách nối các điểm từ i đến j) - tổng các (dp(i,k) * (số cách nối các điểm từ k đến j)) với k chạy từ i đến j.

Lưu ý rằng đầu tiên ta phải kiểm tra xem có điểm nào nằm giữa i và j nối ra ngoài đoạn từ i đến j không, vì nếu có thì ta không thể có được thành phần (i,j).

Mỗi loại thành phần (i,j) sẽ xuất hiện trong (số cách nối các điểm nằm ngoài đoạn i đến j) cách nối, do đó đáp án sẽ là tổng các (dp(i,j)*(số cách nối các điểm nằm ngoài đoạn i đến j)).

Code (Java)