P10564: 安放炸弹
传统题
1.000s
时间限制
128MB
内存限制
3 提交
2 解决
【题目描述】
【题目描述】
小蔡决定在小头家门口安放炸弹！！
小头家门口有n个连续的格子排成一行，对于每个格子，小蔡可以决定放一颗炸弹或者不放。为了防止小头被炸死，小蔡不会在连续3个格子都放上炸弹。小蔡想知道一共有多少安放炸弹的方案(可以一个也不放)。
由于方案数可能很多，所以你只需要方案个数mod 55555就可以了。
【输入格式】
一个正整数，即n
【输出格式】
仅包含一个整数，即答案
【输出样例】
样例1：4
样例2：5
【输出样例】
样例1：13
样例2：24
【样例解释】
对于样例1的解释，一共有4个格子，每个格子可以选择放或者不放，因此根据乘法原理共有2*2*2*2=16种方案，其中在（1，2，3）上放炸弹是不合法的，会炸死小头。同样（2，3，4）和（1，2，3，4）也都不合法，所以一共有16-3=13种方案
13 mod 55555=13，因此答案为13
【数据规模】
70%的数据，n≤20
100%的数据，n≤1000