Tạm gác hết những âu lo lại :v cùng mình giải bài toán này nhé. Mình cho các bạn một xâu kí tự gồm chữ cái in thường và một số nguyên . Bạn hãy giúp mình đếm số xâu kí tự độ dài cũng chỉ gồm các chữ cái in thường thỏa mãn điều kiện sau đây: Có chính xác cặp số nguyên với và xâu con liên tiếp của từ vị trí đến vị trí có thứ tự từ điển lớn hơn xâu con liên tiếp của từ vị trí đến vị trí .
Nhắc lại, xâu được gọi là có thứ tự từ điển lớn hơn xâu khi và chỉ khi tồn tại chỉ số sao cho:
Với mọi chỉ số sao cho , ta luôn có .
Ví dụ, "tranchau" có thứ tự từ điển lớn hơn "tocotoco", "anhhanh" có thứ tự từ điển lớn hơn "anhanhh", "nguvanloi" có thứ tự từ điển lớn hơn "bichphuong", "thilin" có thứ tự từ điển lớn hơn "thaozi", "ntha" có thứ tự từ điển lớn hơn "dxmh".
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ hai chứa xâu kí tự gồm chữ cái in thường.
Dữ liệu ra:
In ra một số nguyên duy nhất là số xâu kí tự thỏa mãn điều kiện trên. Do kết quả có thể rất lớn, bạn chỉ cần in ra đáp số theo modulo .
Ví dụ:
Dữ liệu vào:
2 2
yy
Dữ liệu ra:
26
Dữ liệu vào;
2 3
yy
Dữ liệu ra:
1
Giải thích:
Trong ví dụ thứ nhất, ta có xâu là "yy". Khi đó, xâu là "za" thỏa mãn vì:
Với và , ta có "z" > "y".
Với và , ta có "a" < "y".
Với và , ta có "za" > "yy".
Như vậy, có chính xác cặp chỉ số để xâu con liên tiếp từ đến ở có thứ tự từ điển lớn hơn xâu con liên tiếp từ đến ở .
Tương tự, xâu "yz" cũng thỏa mãn vì:
Với và , ta có "y" = "y".
Với và , ta có "z" > "y".
Với và , ta có "yz" > "yy".
Như vậy, có chính xác cặp chỉ số để xâu con liên tiếp từ đến ở có thứ tự từ điển lớn hơn xâu con liên tiếp từ đến ở .
Ngược lại, xâu "az" không thỏa mãn vì:
Với và , ta có "a" < "y".
Vơi và , ta có "z" > "y".
Với và , ta có "az" < "yy".
Như vậy, chỉ có cặp chỉ số để xâu con liên tiếp từ đến ở có thứ tự từ điển lớn hơn xâu con liên tiếp từ đến ở .
Tương tự, xâu "zz" cũng không thỏa mãn vì:
Với và , ta có "z" > "y".
Vơi và , ta có "z" > "y".
Với và , ta có "zz" > "yy".
Như vậy, có tới cặp chỉ số để xâu con liên tiếp từ đến ở có thứ tự từ điển lớn hơn xâu con liên tiếp từ đến ở .
xâu kí tự thỏa mãn điều kiện đề bài trong ví dụ thứ nhất là: "yz", "za", "zb",..., "zy".
Trong ví dụ thứ hai, "zz" là xâu duy nhất thỏa mãn điều kiện đề bài.
Giới hạn:
Bộ test của bài được chia làm các subtask như sau:
Subtask ( số điểm): ;
Subtask ( số điểm): ;
Subtask ( số điểm): và ;
Subtask ( số điểm): ;
Subtask ( số điểm): Xâu chỉ gồm kí tự ;
Subtask ( số điểm còn lại): Không có ràng buộc gì thêm.
