Cầu thang nhà A Phủ - LCOJ: Luyen Code Online

DPSTEPS - Cầu thang nhà A Phủ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Hôm nay Bờm đến thăm nhà A Phủ, A Phủ ở nhà sàn, để lên nhà A Phủ phải đi bằng cầu thang. Cầu thang nhà A Phủ có ~N~ bậc, trong đó có ~K~ bậc đã bị mục nên không thể bước lên được (nhà A Phủ rất nghèo, từ ngày cấm trồng cây anh túc thì nhà A Phủ sống rất khó khăn). Chú ý: Bậc thứ ~N~ là sàn nhà A Phủ, bậc này không bị hỏng. Do đi đường mệt nên Bờm chỉ còn sức để có thể bước mỗi lần một hoặc tối đa hai bậc thang mà thôi. Vừa định bước lên cầu thang thì Bờm chợt nầy ra một câu hỏi: Có bao nhiêu cách bước từ sân lên nhà A Phủ? Các em hãy tính giúp Bờm nhé.

Input

Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ cách nhau bởi một dấu cách;
Dòng thứ hai chứa ~K~ số nguyên dương ~b_1, b_2, …, b_K~ là chỉ số các bậc thang bị hỏng, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

~1 ≤ N ≤ 10^5; 0 ≤ K ≤ N; 1 ≤ b_i < N~.

Output

Một số nguyên duy nhất là số cách bước lên nhà A Phủ (do số cách có thể rất lớn nên ta chỉ lấy phần dư khi chia cho 1000000007 ).

Sample

Input #1

5 1
2

Output #1

Hint

Bờm có thể bước như sau: ~1→3→4→5~ hoặc ~1→3→5~, do đó có 2 cách.

Problem source: Chuyên Sơn La Online Judge

Bình luận

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

include <iostream>

include <vector>

include <algorithm>

const int MOD = 1000000007;

int main() { int n, m; std::cin >> n >> m;

std::vector<int> broken_steps(m);
for (int i = 0; i < m; ++i) {
    std::cin >> broken_steps[i];
}

std::sort(broken_steps.begin(), broken_steps.end());

std::vector<int> dp(n + 1, 0);
dp[0] = 1;

for (int i = 1; i <= n; ++i) {
    if (std::binary_search(broken_steps.begin(), broken_steps.end(), i)) {
        // Bậc thang i bị hỏng, không thể bước lên được
        dp[i] = 0;
    } else {
        // Cập nhật số cách bước lên bậc i dựa trên các bậc trước đó
        if (i >= 2) {
            dp[i] = (dp[i] + dp[i - 2]) % MOD;
        }
        dp[i] = (dp[i] + dp[i - 1]) % MOD;
    }
}

std::cout << dp[n] << std::endl;

return 0;

}