VO 19 Bài 5 - Ca sỹ Lệ Quyên


Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Lệ Quyên (sinh năm ~1981)~ là một nữ ca sỹ chuyên đi trình diễn tại Việt Nam. Cô nổi tiếng với nhiều dòng nhạc khác nhau, bao gồm nhạc trẻ và Bolero. Những ngườisinh ra vào những năm ~1980~, hoặc là một fan yêu thích dòng nhạc xanh của hơn ~10~ năm trước, hẳn sẽ biết tới tên tuổi của Lệ Quyên qua những bài hát như Giấc mơ có thật hay Thôi đừng chiêm bao. Sinh ra trong một gia đình giàu truyền thống nghệ thuật, Lệ Quyên sớm bộc lộ năng khiếu bẩm sinh về âm nhạc ngay ở độ tuổi nhi đồng.

Chuyện không kể rằng, từ nhỏ, Lệ Quyên thường tự tạo ra những bản nhạc riêng để luyện giọng. Những bản nhạc đó giai điệu chán ngắt, nhưng lại giúp người hát luyện tập cao độ hiệu quả. Mỗi bản nhạc của cô chứa ~N + 1~ nốt nhạc, hai nốt liên tiếp nhau cách nhau đúng một cung. Một đoạn nhạc gồm ~D~ nốt nhạc liên tiếp được coi là có cao độ ổn định khi và chỉ khi chênh lệch giữa nốt cao nhất và nốt trầm nhất của đoạn nhạc đó là tối đa một cung. Trong một ngày, nữ ca sỹ muốn tạo ra các bản nhạc có chính xác ~T~ đoạn nhạc gồm ~D~ nốt nhạc liên tiếp có cao độ ổn định. Cô thắc mắc cô có thể tạo ra bao nhiêu bản nhạc khác nhau thoả mãn điều kiện này. Hai bản nhạc được coi là khác nhau khi và chỉ khi không tồn tại một cách dịch giọng nào biến bản nhạc thứ nhất thành bản nhạc thứ hai.

Nói cách khác, nếu ta biểu diễn cao độ của bản nhạc bởi dãy số ~A_0~, ~A_1~, ~\dots~, ~A_N~, bạn cần đếm số dãy thoả mãn:

  • ~A_0 = 0~. Với mọi ~1 \leq i \leq N~, ~(A_i~ − Ai−1)^2 ~= 1~.
  • Có chính xác ~T~ chỉ số ~i~ phân biệt thoả mãn ~0 \leq i \leq N~ − ~D + 1~ và: $$\max_{i \leq j \leq i + D-1} A_j - \min_{i \leq j \leq i + D-1} A_j \leq 1$$

Do số dãy số thoả mãn có thể rất lớn, bạn chỉ cần ghi ra kết quả theo modulo ~998\,244\,353~.

Input

  • Một dòng duy nhất chứa ba số nguyên ~N~, ~D~ và ~T~ ~(1 \leq N \leq 6420~, ~2 \leq D \leq N + 1~, ~0 \leq T \leq N - D + 2)~

Output

Một số nguyên duy nhất là số bài hát modulo ~998\,244\,353~.

Giới hạn

  • Subtask ~1~ ~(20/70~ điểm): ~N \leq 20~
  • Subtask ~2~ ~(23/70~ điểm): ~N \leq 420~
  • Subtask ~3~ ~(27/70~ điểm): ~N \leq 6420~

Sample Input 1

5 4 2

Sample Output 1

4

Sample Input 2

4 3 2

Sample Output 2

6

Giải thích

  • Trong ví dụ đầu tiên, các bản nhạc thoả mãn có dãy cao độ là: ~(0~, ~1~, ~2~, ~1~, ~2~, ~1)~, ~(0~, ~-1~, ~0~, ~-1~, ~0~, ~1)~, ~(0~, ~-1~, ~-2~, ~-1~, ~-2~, ~-1)~, ~(0~, ~1~, ~0~, ~1~, ~0~, ~-1)~
  • Trong ví dụ thứ hai, các bản nhạc thoả mãn có dãy cao độ là: ~(0~, ~-1~, ~0~, ~-1~, ~-2)~, ~(0~, ~1~, ~2~, ~1~, ~2)~, ~(0~, ~1~, ~0~, ~1~, ~2)~, ~(0~, ~-1~, ~-2~, ~-1~, ~-2)~, ~(0~, ~-1~, ~0~, ~1~, ~0)~, ~(0~, ~1~, ~0~, ~-1~, ~0)~

Comments

There are no comments at the moment.