VM 08 Bài 01 - Bậc thang

View as PDF
Submit solution
Points: 0.06 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
VNOI Marathon '08 - Round 1/DivBProblem Setter: Ngô Minh Ðức
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -5
    tandochuyentin2022  commented on Feb. 19, 2025, 1:47 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    NVTai  commented on Feb. 11, 2025, 2:46 p.m.

    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


    • -2
      hahuy0928  commented on Feb. 18, 2025, 5:24 p.m.

      :)))) may quá


  • -1
    tanhphungvivo2009  commented on Jan. 13, 2025, 11:54 a.m.

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


  • 0
    nhpnuyn  commented on Nov. 6, 2024, 1:40 a.m. ← edited

    bài hay quá


  • -11
    kentran232  commented on Sept. 16, 2024, 8:51 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -2
    Soda12  commented on Aug. 10, 2024, 2:52 a.m.

    hehe


  • -3
    hoanglongnguyen9002  commented on July 24, 2024, 1:08 p.m. ← edited

    cho em hoi bai nay lam sao a?


    • -18
      hieudeptrai  commented on July 24, 2024, 1:10 p.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -13
        sunshine262  commented on July 24, 2024, 1:10 p.m. ← edited

        This comment is hidden due to too much negative feedback. Show it anyway.


        • -10
          xingyi  commented on July 24, 2024, 1:10 p.m. ← edited

          This comment is hidden due to too much negative feedback. Show it anyway.


          • -10
            kimchi5e4  commented on July 24, 2024, 1:11 p.m. ← edited

            This comment is hidden due to too much negative feedback. Show it anyway.


            • -9
              YoruNiKakeru  commented on July 24, 2024, 1:12 p.m. ← edited

              This comment is hidden due to too much negative feedback. Show it anyway.


              • -11
                hieuz08  commented on July 24, 2024, 1:13 p.m.

                This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    melondepchai  commented on June 29, 2024, 5:25 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -18
    jard  commented on May 10, 2024, 11:03 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    how_to_get_her_love999  commented on Jan. 5, 2024, 2:34 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -9
    Cuunon311  commented on Oct. 9, 2023, 6:03 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    kakapy  commented on Oct. 9, 2023, 1:13 p.m.

    day fibonaci


  • -10
    nogo007akapkn  commented on Sept. 23, 2023, 3:18 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -6
      __int128  commented on May 22, 2024, 3:50 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -22
    reddevils2709  commented on Feb. 23, 2023, 7:31 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.