问题 26085 --炸弹安放

26085: 炸弹安放

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 2
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

题目描述

【题目描述】

 

小蔡决定在小头家门口安放炸弹!!

小头家门口有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

输入

输出

提示

来源

[提交][状态]