PERREC - Perfect Rectangles
Giới hạn- Thời gian: 0.572s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 1 bảng kích thước N * N được chia thành các ô vuông đơn vị. Mỗi ô vuông có thể có màu đen hoặc trắng. Bây giờ, định nghĩa 1 hình chữ nhật tốt là 1 hình chữ nhật có các cạnh song song với cạnh của bảng và chỉ chứa các ô vuông màu trắng. 1 hình chữ nhật được gọi là hoàn hảo, nếu nó là 1 hình chữ nhật tốt, và không tồn tại 1 hình chữ nhật tốt nào khác chứa nó (tức không thể mở rộng hình chữ nhật này sang trái, phải, trên hay dưới).
Yêu cầu: Xác định số hình chữ nhật hoàn hảo của bảng đã cho.
Lưu ý:
Để giảm kích thước của input, bảng sẽ được tô màu theo quy tắc sau:
- Ban đầu bảng chỉ chứa các ô vuông màu trắng
- Sinh 2 dãy số X và Y độ dài m theo quy tắc
- X[0] = x0 mod N, Y[0] = y0 mod N
- X[i] = (X[i – 1] * a + b) mod N, Y[i] = (Y[i – 1] * c + d) mod N với 1 <= i < m,
- trong đó x0, y0, a, b, c, d, m là các số được cho trước, và P mod Q kí hiệu là phần dư của phép chia P cho Q
- Tô đen các ô có tọa độ (X[0],Y[0]), (X[1],Y[1]),…, (X[m – 1],Y[m – 1]). (Tọa độ của bảng được đánh số từ 0 đến N – 1 theo thứ tự từ trái qua phải, và từ trên xuống dưới)
Input:
- 1 dòng duy nhất gồm 8 số nguyên N,m,x0,a,b,y0,c,d như mô tả trong đề bài
Output:
- 1 dòng duy nhất ghi ra số lượng hình chữ nhật hoàn hảo thu được
Giới hạn:
- 0 < N <= 2000
- 1 <= m <= 4000000
- 0 <= a,b,c,d,x0,y0 <= 2000
Example:
Input 1 5 1 2 0 0 2 0 0 Output 1 4 Input 2 4 4 0 1 1 0 1 1 Output 2 6 Input 3 10 20 4 76 2 6 2 43 Output 3 12
- Người up: huy391992
- Nguồn bài: SRM 431 Div 1, Level Three