TLEoj Contest #05 - Đếm bảng ký tự

Xem PDF

Nộp bài


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

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

Cho một bảng kí tự gồm n hàng và m cột. Các hàng được đánh số từ 1→n từ trên xuống dưới, và các cột được đánh số từ 1→m từ trái sang phải. Bạn có thể thực hiện thao tác sau vô hạn lần (hoặc không thực hiện lần nào):

  • Chọn hàng thứ i trên bảng, và đẩy kí tự đầu tiên của hàng đó ra phía sau của hàng (1≤i≤n) (ví dụ với xâu \text{haudepzai} thì nếu để kí tự đầu tiên vào sau hàng thì sẽ là \text{audepzaih})

Hãy tính xem, với vô số cách xoay bảng, có thể có bao nhiêu cách thực hiện thao tác sao cho sẽ có một xâu đối xứng xuất hiện tại cột thứ nhất? Biết rằng, hai cách thực hiện xoay bảng được tính là khác nhau khi bảng kí tự được tạo ra sau khi xoay bằng hai cách là khác nhau.

Explanation

Chúng ta tạm gọi c_i là số lần thực hiện thao tác ở hàng thứ i (và mảng C = \left\{c_1, c_2, c_3, ..., c_n\right\} thể hiện một cách xoay bảng).
Giả sử chúng ta có một bảng như sau: P = \left[\begin{array}{c} \text{aba} \\ \text{bba} \\ \text{cba} \end{array}\right] (có n = m = 3).
Hai cách xoay bảng PC_1 = \left\{1, 2, 1\right\}C_2 = \left\{2, 1, 2\right\} được xem là hai cách khác nhau vì:

  • Bảng được tạo thành đối với cách thứ nhất và cách thứ 2 lần lượt là P_1 = \left[\begin{array}{c} \text{baa} \\ \text{abb} \\ \text{bac} \end{array}\right], P_2 = \left[\begin{array}{c} \text{aab} \\ \text{bab} \\ \text{acb} \end{array}\right];
  • P_1 \ne P_2 \Rightarrow hai cách xoay bảng C_1C_2 là khác nhau.

Còn đối với hai cách xoay bảng PC_1 (như trên) và C_3 = \left\{4, 8, 1\right\}, chúng được xem là giống nhau vì sau khi thực hiện cả hai cách này thì đều cho bảng P' = \left[\begin{array}{c} \text{baa} \\ \text{abb} \\ \text{bac} \end{array}\right].

Input, Output và Subtasks

Input

Dòng 1 gồm số q là các bộ test con (subtest) cần được xử lý (1\le q\le 50).

Mỗi bộ test con gồm các dữ liệu như sau:

  • Dòng 1 gồm hai số n, m (1\le n, m\le 10^3);
  • n dòng sau, mỗi dòng gồm có m kí tự Latinh thường, giữa hai kí tự bất kì trong 1 dòng không có khoảng trắng.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

Gồm q dòng là kết quả cho q subtest. Mỗi truy vấn thứ i có giá trị k_i chỉ số cách xoay bảng tạo xâu đối xứng tại cột thứ nhất với bảng của subtest thứ i.

Lưu ý: Vì các kết quả có thể rất lớn nên các bạn cần in kết quả dưới dạng phần dư của phép chia kết quả cho 10^9+7.

Subtasks
  • Subtask 1 (7.5\%): n,m\le 7,q\le 2
  • Subtask 2 (22.5\%): q\le 10
  • Subtask 3 (70\%): Không có ràng buộc gì thêm

Sample 1

Input
2
2 2
ac
ab
3 3
aba
bba
cba
Output
1
9
Note

Testcase #1: Giữ nguyên bảng và ta sẽ có được xâu đối xứng ở cột thứ nhất của bảng ("\text{aa}")
Testcase #2: Các bảng thỏa mãn bao gồm: \left[\begin{array}{c} \text{aba} \\ \text{bba} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{aba} \\ \text{bab} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{aba} \\ \text{abb} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{aab} \\ \text{bba} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{aab} \\ \text{bab} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{aab} \\ \text{abb} \\ \text{acb} \end{array}\right], \left[\begin{array}{c} \text{baa} \\ \text{bba} \\ \text{bac} \end{array}\right], \left[\begin{array}{c} \text{baa} \\ \text{bab} \\ \text{bac} \end{array}\right], \left[\begin{array}{c} \text{baa} \\ \text{abb} \\ \text{bac} \end{array}\right]


Bình luận

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