Collection Game

C.Collection Game

Time Limit: 1000 MS Memory Limit: 128000 K Total Submit: 841 (248 users) Total Accepted: 236 (165 users) Special Judge: No

Description

POI and POJ are pair of sisters, one is a master in “Kantai Collection”, another is an excellent competitor in ACM programming competition. One day, POI wants to visit POJ, and the pace that between their homes is made of square bricks. We can hypothesis that POI’s house is located in the NO.1 brick and POJ’s house is located in the NO.n brick. For POI, there are three ways she can choose to move in every step, go ahead one or two or three bricks. But some bricks are broken that couldn’t be touched. So, how many ways can POI arrive at POJ’s house?

Input

There are multiple cases. In each case, the first line contains two integers N(1<=N<=10000) and M (1<=M<=100), respectively represent the sum of bricks, and broke bricks. Then, there are M number in the next line, the K-th number a[k](2<=a[k]<=n-1) means the brick at position a[k] was broke.

Output

Please output your answer P after mod 10007 because there are too many ways.

Sample Input

5 1 3

Sample Output

3 题意： 有一个人住在标号为1 的地方，她想去n这个地方，，每次可以走1或2或3步，但是有些地方破坏了，没法踩。。问你到n时，有几种方法 思路：就是菲波那切数列。。。当时比赛的时候想到这些了，，，但是某些细节没处理好，导致没A出来。，，太可惜了。。。。把破坏的地方为0就行了 #include<stdio.h> #include<iostream> #include<string.h> using namespace std; int a[1000000]; int b[1000000]; int vis[1000000]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=-1) { memset(vis,0,sizeof(vis)); memset(b,0,sizeof(b)); for(int i=0;i<m;i++) { scanf("%d",&a[i]); vis[a[i]]=1; } b[1]=1; if(!vis[2]) b[2]=1; if(!vis[3]) b[3]=b[2]+1; for(int i=4;i<=n;i++) { if(vis[i]==1) b[i]=0; else b[i]=(b[i-1]+b[i-2]+b[i-3])%10007; } printf("%d\n",b[n]); } }