洛谷题目传送门 | AT原题传送门

思路

这其实是一道递推题。

打眼一看，这道题和P1255 数楼梯是差不多的，只不过是本题又新增了一个条件：有 mm 个楼梯是坏的。

如果没有这个条件，我们可以定义，第 ii 阶楼梯的总方案数为 fif_i，从题目中可以很容易得出：fi=fi−1+fi−2(i≥2)f_i=f_{i-1}+f_{i-2}(i \geq 2)，因为只能从第 i−1i-1 和第 i−2i-2 阶楼梯上到第 ii 阶楼梯。

加上那个条件后，我们可以定义一个 bool\texttt{bool} 数组 vis\texttt{vis}，如果第 ii 阶楼梯是坏的，那 visi=truevis_i=true，否则 visi=falsevis_i=false。

有几点需要注意：

  1. 每次递推都需  mod 109+7\bmod 10^9+7；
  2. 如果连续两阶楼梯都是坏的，也就是 visi=truevis_i=true 且 visi−1=truevis_{i-1}=true，直接输出 00 并退出程序（不判断也不会超时）；
  3. 从第 00 阶台阶开始计算；
  4. 赋 f0f_0 和 f1f_1 的初始值时要特判第 00 和第 11 阶楼梯是否损坏。

直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<iostream>
using namespace std;
inline int read()//快读
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mod=1e9+7;
int n,m,a,f[100010];
bool vis[100010]={0};
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		a=read();
		vis[a]=1;//标记该台阶已损坏
		if(vis[a] && vis[a-1])//判断是否有连续两个台阶是坏的
		{
			cout<<0<<endl;
			return 0;
		}
	}
	if(!vis[0])//特判第0和第1阶楼梯是否损坏
	{
		f[0]=1;
	}
	if(!vis[1])
	{
		f[1]=1;
	}
	for(int i=2;i<=n;i++)
	{
		if(vis[i]) f[i]=0;//如果该楼梯损坏，则无法上到该楼梯
		else
		{
			f[i]=(f[i-1]+f[i-2])%mod;//递推式(不要忘了取模)
		}
	}
	cout<<f[n]<<endl;
	return 0;
}

记得结尾要换行哦