Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Leo cầu thang tránh bậc hỏng

    Một cầu thang có nnn bậc, đánh số từ 111 đến nnn. Bạn đứng ở mặt đất (bậc 000) và mỗi bước có thể bước lên 111 hoặc 222 bậc. Tuy nhiên có một số bậc bị hỏng, không được đặt chân lên.

    Hãy đếm số cách khác nhau để leo từ bậc 000 lên đúng bậc nnn mà không bước vào bậc hỏng nào. Vì số cách có thể rất lớn, hãy in ra kết quả theo modulo 109+710^9 + 7109+7.

    Bậc 000 luôn an toàn. Nếu bậc nnn bị hỏng thì không có cách nào (đáp số 000).

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên nnn và mmm — số bậc và số bậc hỏng. Dòng thứ hai chứa mmm số nguyên là các bậc hỏng (nếu m=0m = 0m=0 thì dòng này có thể trống).

    • Ràng buộc đầu vào:

      1≤n≤1061 \le n \le 10^61≤n≤106; 0≤m≤n0 \le m \le n0≤m≤n; các bậc hỏng nằm trong [1,n][1, n][1,n] và đôi một khác nhau.

    • Định dạng đầu ra:

      In ra số cách leo lên bậc nnn, lấy modulo 109+710^9 + 7109+7.

    Ví dụ:

    Đầu vào:

    4 1
2

    Đầu ra:

    1

    Giải thích:

    Bậc 2 hỏng. Cách hợp lệ: 0→1→3→4. Chỉ 1 cách (mọi đường khác đều phải qua bậc 2).

    Đang tải editor...