PVHOI 2.0 - Bài 6: Đi tìm hạnh phúc

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Swift
Điểm: 60 (p) Thời gian: 0.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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ự \(s\) gồm \(n\) chữ cái in thường và một số nguyên \(k\). Bạn hãy giúp mình đếm số xâu kí tự \(t\) độ dài \(n\) 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 \(k\) cặp số nguyên \((l, r)\) với \(1 \leq l \leq r \leq n\) và xâu con liên tiếp của \(t\) từ vị trí \(l\) đến vị trí \(r\)thứ tự từ điển lớn hơn xâu con liên tiếp của \(s\) từ vị trí \(l\) đến vị trí \(r\).

Nhắc lại, xâu \(a = a_1 a_2 \ldots a_n\) được gọi là có thứ tự từ điển lớn hơn xâu \(b = b_1 b_2 \ldots b_n\) khi và chỉ khi tồn tại chỉ số \(i\) sao cho:

  • \(1 \leq i \leq n\)
  • \(a_i > b_i\)
  • Với mọi chỉ số \(j\) sao cho \(1 \leq j < i\), ta luôn có \(a_j = b_j\).

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".

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(k\) \((1 \leq n \leq 2000, 0 \leq k \leq 3000)\).
    Dòng thứ hai chứa xâu kí tự \(s\) gồm \(n\) chữ cái in thường.

Output

  • In ra một số nguyên duy nhất là số xâu kí tự \(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 \(998244353\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

  • Subtask \(1\) (\(8\) điểm): \(n \leq 5\)
  • Subtask \(2\) (\(8\) điểm): \(n \leq 10\)
  • Subtask \(3\) (\(10\) điểm): \(n \leq 200\)\(k \leq 300\)
  • Subtask \(4\) (\(6\) điểm): \(k = 0\)
  • Subtask \(5\) (\(12\) điểm): Xâu \(s\) chỉ gồm kí tự \(a\).
  • Subtask \(6\) (\(16\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(60\) điểm.

Example

Test 1

Input
2 2
yy
Output
26
Note

Trong ví dụ thứ nhất, ta có xâu \(s\) là "yy". Khi đó, xâu \(t\) là "za" thỏa mãn vì:

  • Với \(l = 1\)\(r = 1\), ta có "z" > "y".
  • Với \(l = 2\)\(r = 2\), ta có "a" < "y".
  • Với \(l = 1\)\(r = 2\), ta có "za" > "yy".

Như vậy, có chính xác \(k = 2\) cặp chỉ số \((l, r)\) để xâu con liên tiếp từ \(l\) đến \(r\)\(t\) có thứ tự từ điển lớn hơn xâu con liên tiếp từ \(l\) đến \(r\)\(s\).

Tương tự, xâu "yz" cũng thỏa mãn vì:

  • Với \(l = 1\)\(r = 1\), ta có "y" = "y".
  • Với \(l = 2\)\(r = 2\), ta có "z" > "y".
  • Với \(l = 1\)\(r = 2\), ta có "yz" > "yy".

Như vậy, có chính xác \(k = 2\) cặp chỉ số \((l, r)\) để xâu con liên tiếp từ \(l\) đến \(r\)\(t\) có thứ tự từ điển lớn hơn xâu con liên tiếp từ \(l\) đến \(r\)\(s\).

Ngược lại, xâu "az" không thỏa mãn vì:

  • Với \(l = 1\)\(r = 1\), ta có "a" < "y".
  • Vơi \(l = 2\)\(r = 2\), ta có "z" > "y".
  • Với \(l = 1\)\(r = 2\), ta có "az" < "yy".

Như vậy, chỉ có \(1\) cặp chỉ số \((l, r)\) để xâu con liên tiếp từ \(l\) đến \(r\)\(t\) có thứ tự từ điển lớn hơn xâu con liên tiếp từ \(l\) đến \(r\)\(s\).

Tương tự, xâu "zz" cũng không thỏa mãn vì:

  • Với \(l = 1\)\(r = 1\), ta có "z" > "y".
  • Vơi \(l = 2\)\(r = 2\), ta có "z" > "y".
  • Với \(l = 1\)\(r = 2\), ta có "zz" > "yy".

Như vậy, có tới \(3\) cặp chỉ số \((l, r)\) để xâu con liên tiếp từ \(l\) đến \(r\)\(t\) có thứ tự từ điển lớn hơn xâu con liên tiếp từ \(l\) đến \(r\)\(s\).

\(26\) 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".

Test 2

Input
2 3
yy
Output
1
Note

Trong ví dụ thứ hai, "zz" là xâu duy nhất thỏa mãn điều kiện đề bài.


Bình luận


  • 1
    Lê_Gia_Khánh 7:54 p.m. 22 Tháng 10, 2021

    Bài hay mà ;-;


    • 9
      dang7rickroll 9:08 p.m. 18 Tháng 10, 2021

      Ủa sao bài văn ở trên mất rồi GS ơi ?? Em đang định tìm đọc lại