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 m và n cột đánh số từ 1 đến n, với phần tử ở hàng i cột j là a[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ứ i là 1, 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