VM 08 Bài 01 - Bậc thang

Xem dạng PDF
Gửi bài giải
Điểm: 0,06 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
VNOI Marathon '08 - Round 1/DivBProblem Setter: Ngô Minh Ðức
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm ~N~ bậc.

Các bậc thang được đánh số từ 1 đến ~N~ từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng).

Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ ~N~). Bờm muốn nhờ bạn trả lời câu hỏi này.

Input

Dòng đầu tiên: gồm 2 số nguyên ~N~ và ~K~, là số bậc của cầu thang và số bậc thang bị hỏng ~(0 \le K < N \le 10^5)~.

Dòng thứ hai: gồm ~K~ số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.

Output

In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008.

Sample Input 1

4 2
2 3

Sample Output 1

0

Sample Input 2

90000 1
49000

Sample Output 2

4108266

Bình luận

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


  • -7
    tandochuyentin2022  đã bình luận lúc 19, Tháng 2, 2025, 13:47

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -2
    NVTai  đã bình luận lúc 11, Tháng 2, 2025, 14:46

    bài này tui thấy thuật toán fibonacci áp dụng vào thì nó sẽ không ra đúng đán án, phải biến đổi một chút là dp[2]=1 thì mới đúng, b nào thây như vậy thì upvote cho mình với


    • -4
      hahuy0928  đã bình luận lúc 18, Tháng 2, 2025, 17:24

      :)))) may quá


  • -2
    tanhphungvivo2009  đã bình luận lúc 13, Tháng 1, 2025, 11:54

    bài này dp là được


  • -1
    nhpnuyn  đã bình luận lúc 6, Tháng 11, 2024, 1:40 ← chỉnh sửa

    bài hay quá


  • -12
    kentran232  đã bình luận lúc 16, Tháng 9, 2024, 8:51

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -2
    Soda12  đã bình luận lúc 10, Tháng 8, 2024, 2:52

    hehe


  • -3
    hoanglongnguyen9002  đã bình luận lúc 24, Tháng 7, 2024, 13:08 ← chỉnh sửa

    cho em hoi bai nay lam sao a?


    • -18
      hieudeptrai  đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -13
        sunshine262  đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


        • -10
          xingyi  đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa

          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


          • -10
            kimchi5e4  đã bình luận lúc 24, Tháng 7, 2024, 13:11 ← chỉnh sửa

            Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


            • -9
              YoruNiKakeru  đã bình luận lúc 24, Tháng 7, 2024, 13:12 ← chỉnh sửa

              Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


              • -11
                hieuz08  đã bình luận lúc 24, Tháng 7, 2024, 13:13

                Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    melondepchai  đã bình luận lúc 29, Tháng 6, 2024, 5:25

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -18
    jard  đã bình luận lúc 10, Tháng 5, 2024, 11:03

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -12
    how_to_get_her_love999  đã bình luận lúc 5, Tháng 1, 2024, 2:34 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -9
    Cuunon311  đã bình luận lúc 9, Tháng 10, 2023, 18:03

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 0
    kakapy  đã bình luận lúc 9, Tháng 10, 2023, 13:13

    day fibonaci


  • -10
    nogo007akapkn  đã bình luận lúc 23, Tháng 9, 2023, 3:18

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -6
      __int128  đã bình luận lúc 22, Tháng 5, 2024, 3:50

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -22
    reddevils2709  đã bình luận lúc 23, Tháng 2, 2023, 19:31

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.