Phân nhóm tham lam
Đề bài
Mô tả
Cho dãy gồm phần tử và một số nguyên . Hãy chọn một tập các đoạn thỏa mãn:
- mỗi đoạn gồm các phần tử liên tiếp của ,
- mỗi đoạn có ít nhất phần tử,
- các phần tử trong cùng một đoạn đôi một khác nhau,
- không có hai đoạn nào chung phần tử, tức là mỗi phần tử của thuộc tối đa một đoạn.
Nhiệm vụ của bạn là tìm số đoạn lớn nhất có thể chọn, và đếm số cách chọn các đoạn để đạt được số lượng lớn nhất đó.
Hai cách chọn được coi là khác nhau nếu xảy ra một trong hai điều sau:
- Có một phần tử thuộc một đoạn nào đó trong cách này nhưng không thuộc đoạn nào trong cách kia.
- Có hai phần tử và thuộc cùng một đoạn trong cách này nhưng thuộc hai đoạn khác nhau trong cách kia.
Để bài toán khó hơn một chút, bạn được cho thêm số nguyên . Với mỗi giá trị , hãy giải bài toán trên với .
Dữ liệu vào
Dòng đầu tiên chứa số bộ test .
Mỗi bộ test gồm ba dòng:
- Dòng thứ nhất chứa hai số nguyên và (, ).
- Dòng thứ hai chứa số nguyên ().
- Dòng thứ ba chứa số nguyên ().
Dữ liệu đảm bảo tổng trên tất cả các bộ test không vượt quá , và tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra dòng. Dòng thứ chứa kết quả của bài toán với , gồm hai số nguyên cách nhau bởi dấu cách:
- số đoạn lớn nhất có thể chọn,
- số cách chọn các đoạn để đạt được số lượng lớn nhất đó, lấy modulo .
Ràng buộc
- ,
- ,
- Tổng và tổng trên tất cả các bộ test đều không vượt quá
Ví dụ
Ký hiệu là đoạn gồm các phần tử .
| Input | Output | Giải thích |
|---|---|---|
| 2 5 2 1 2 1 2 1 2 3 6 2 1 2 3 4 5 6 3 5 |
2 3 0 1 2 1 1 3 |
Bộ test thứ nhất, : chọn được tối đa đoạn, có cách: và ; và ; và . Với , không có đoạn nào dài ít nhất gồm các phần tử đôi một khác nhau (chỉ có một cách là không chọn gì). Bộ test thứ hai, : cách duy nhất là và . Với : chỉ chọn được một đoạn, là một trong , , . |
| 1 4 4 1 2 3 1 3 1 4 2 |
1 2 4 1 0 1 2 1 |
: một đoạn, hoặc . : mỗi phần tử là một đoạn. : không chọn được đoạn nào. : chỉ có và . |
Bình luận