3271: 覆盖墙壁
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:6
解决:6
题目描述
你有一个长为N宽为2的墙壁,给你两种转头:一个长2宽1,另一个是L型覆盖3个单元的转头。如下图: 转头可以旋转,两种转头可以无限制提供。你的任务是计算用这两种来覆盖N*2的墙壁的覆盖方法。例如一个2*3的墙可以有5种覆盖方法,如下:
注意可以使用两种转头混合起来覆盖,如2*4的墙可以这样覆盖:
给定N,要求计算2*N的墙壁的覆盖方法。由于结果很打,所以只要求出输出最后4位。例如2*13的覆盖方法为13465,只需输出3465即可。如果答案少于4位,就直接输出就可以,不用加0,如N=3时输出5.
输入
一个整数N(1<=n<=1000000),表示墙壁的长。
输出
输出覆盖方法的最后4位,如果不足4位就输出整个答案。
样例输入 复制
13
样例输出 复制
3465