Bulls and Cows

Xem dạng PDF

Gửi bài giải


Điểm: 0,13 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
BaseD on USACO 07
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân john muốn sắp xếp ~n~ con bò(bao gồm cả bò đực và bò cái) của ông ta trên ~1~ hàng. Ông ta biết rằng những con bò đực rất hung hăng -- Nếu ~2~ con bò đực đứng quá gần nhau thì chúng sẽ trở nên hung dữ và bắt đầu húc nhau, vì thế chúng sẽ phá hòng mất trật tự trên hàng mà ông ta vừa sắp xếp được.

Theo kinh nghiệm lâu năm của mình, john biết được nếu ở giữa hai con bò đực có ít nhất ~K~ con bò cái thì sẽ ngăn chặn được việc chúng húc nhau (+_+)

Vì thế, ông ta nhờ các Vcoders giúp đỡ để tính toán xem có bao nhiêu cách sắp xếp đàn bò của ông ta lại sao cho không có "chiến tranh" xảy ra giữa những chú bò (\^_\^), (Tất cả những con bò đực và những con bò cái đều giống nhau). Hai dãy (~B_1~ ...~B_n~) và (~A_1~ ...~A_n~) được cho là khác nhau nếu tồn tại một vị trí ~I~ (~1 \le i \le n~) sao cho ~A_i < > B_i~

Input

  • Gồm ~1~ dòng duy nhất chứa ~2~ số ~n~ và ~k~ cách nhau ~1~ dấu cách
  • ~1 \le N \le 10^{5}~. ~0 \le k \le n~.
  • Có 1/3 số test với ~n \le 15~

Output

  • Gồm duy nhất một số là kết quả theo modun 2111992

Sample Input

4 2

Sample Output

6

Note

C=bò cái, B:bò đực

CCCC
BCCC
CBCC
CCBC
CCCB
BCCB

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.