Biểu thức
Đề bài
Mô tả
Cho một danh sách gồm số phân biệt, Jack muốn tạo các biểu thức chỉ dùng các số trong danh sách cùng với phép cộng, phép nhân và dấu ngoặc (mỗi số có thể được dùng nhiều lần). Jack định nghĩa quan hệ "" giữa hai biểu thức như sau:
- và
- và
- Nếu và thì
Hai biểu thức và được coi là giống nhau khi và chỉ khi .
Hãy đếm số biểu thức khác nhau có giá trị bằng .
Dữ liệu vào
Dòng đầu tiên chứa () là số bộ dữ liệu. Mỗi bộ dữ liệu có dạng sau:
- Dòng đầu tiên chứa hai số ().
- Dòng thứ hai chứa số là các số trong danh sách.
Dữ liệu đảm bảo tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in đáp án trên một dòng. Vì đáp án có thể rất lớn, hãy in nó theo modulo .
Ràng buộc
- .
- , .
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 1 1 1 99 2 5 5 1 2 3 4 5 1 10 1 8 5000 2 3 5 7 11 13 17 19 |
1 0 10 10 299891645 |
Ở bộ thứ ba, có thể biểu diễn bằng , , , , , , , , , . Ở bộ thứ tư, có thể biểu diễn bằng , , , , , , , , , . |
| 2 1 4 2 2 6 2 3 |
2 4 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: và . Bộ thứ hai: , , và . |
Bình luận