TLEoj Contest #01 - Ma trận đối xứng

Xem PDF

Nộp bài

Điểm: 1100 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M
Input: bàn phím
Output: màn hình

Tác giả:
Dạng bài

Một ma trận m \times n, gồm m hàng đánh số từ 1 đến mn cột đánh số từ 1 đến n, với phần tử ở hàng i cột ja[i][j] có thể có một số tính chất sau (có thể không có, có một hoặc có nhiều tính chất cùng một lúc):

  • Tính chất đối xứng qua trục dọc: a[i][j] = a[i][n + 1 - j] với mọi cặp số nguyên (i, j).
  • Tính chất đối xứng qua trục ngang: a[i][j] = a[m + 1 - i][j] với mọi cặp số nguyên (i, j).
  • Tính chất đối xứng qua tâm: a[i][j] = a[m + 1 - i][n + 1 - j] với mọi cặp số nguyên (i, j).

Ví dụ:

  • Ma trận dưới đây là ma trận đối xứng qua trục dọc:
    1221
    3443
    5445
    
  • Ma trận dưới đây là ma trận đối xứng qua trục ngang:
    1234
    5678
    1234
    
  • Ma trận dưới đây là ma trận đối xứng qua tâm:
    1234
    5665
    4321
    

Xét tất cả các ma trận a có thể gồm các số nguyên không âm, với a[i][j] \le b[i][j] cho trước, bạn cần tính số ma trận thỏa mãn một số tính chất trong các tính chất trên.

Input, Output và Subtasks

Input: (bàn phím)
  • Dòng đầu tiên gồm hai số nguyên dương m, n (m, n \le 5000) là số hàng và cột của ma trận a (và cả ma trận b).
  • Dòng thứ hai gồm một chuỗi ba ký tự 0 hoặc 1, trong đó nếu ký tự thứ i1, bạn sẽ cần tính số ma trận thỏa mãn tính chất thứ i theo thứ tự trên đề bài (ví dụ: chuỗi ký tự là 011 thì bạn cần phải đếm số ma trận thỏa mãn tính chất 2 và 3 trên đề bài).
  • m dòng tiếp theo, mỗi dòng gồm một xâu ký tự chỉ gồm các ký tự số. Ký tự thứ j ở dòng thứ i trong m dòng này là phần tử b[i][j].
Output: (màn hình)
  • Một dòng duy nhất gồm số lượng ma trận thỏa mãn các tính chất trong input. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho 10^9 + 7.
Subtasks
  • Subtask 1 (60\%): Chuỗi ký tự ở dòng thứ hai có ít nhất hai ký tự 1.
  • Subtask 2 (40\%): Không có giới hạn gì thêm.

Sample 1

Input (bàn phím)
3 4
001
1010
0101
1010
Output (màn hình)
1
Notes
  • Input yêu cầu đếm số ma trận thỏa mãn tính chất đối xứng tâm, và ma trận gồm toàn số 0 là ma trận duy nhất thỏa mãn.

Bình luận

Không có bình luận nào.