指正翻译
应该是
有 n 级台阶,有 m 级台阶不能走,分别为a_1,a_2...a_m级台阶。
思路:
由于
所以当我们在第i个台阶的时候[链接登录后可见]$,我们可能从i-1级跳上去,也有可能从i-2级跳上去
code:
/*
边界:
f[0]=1,f[1]=1;
递推式:
f[i]=(f[i-1]+f[i-2])%MOD;
特殊情况:
如果此条路被破坏,解的总数为0
解:
f[n]
*/
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int n,cnt,m,a[114514],ans,tmp;
int f[1919810];
/*
a[i]的值如果为1,表示此条路被破坏,走不通
否则,可以走通
*/
int main() {
cin>>n>>m;
while(m--) cin>>tmp,a[tmp]=1;//标记,tmp这条路被破坏
if(!a[0]) f[0]=1;//注意判断第0条路是否被破坏
if(!a[1]) f[1]=1;
for(int i=2;i<=n;i++)
if(!a[i]) //!a[i]也就是a[i]==0,判断是否被破坏
f[i]=(f[i-1]+f[i-2])%MOD;
cout<<f[n]<<endl;//解就是f[n]
return 0;
}