P1990 覆盖墙壁

· · 个人记录 

题目描述  
你有一个长为N宽为2的墙壁，给你两种砖头：一个长2宽1，另一个是L型覆盖3个单元的砖头。如下图：  
0  0  
0  00  
砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖N*2的墙壁的覆盖方法。例如一个2*3的墙可以有5种覆盖方法，如下：  

012 002 011 001 011    
012 112 022 011 001  
注意可以使用两种砖头混合起来覆盖，如2*4的墙可以这样覆盖：  

0112
0012    
给定N，要求计算2*N的墙壁的覆盖方法。由于结果很大，所以只要求输出最后4位。例如2*13的覆盖方法为13465,只需输出3465即可。如果答案少于4位，就直接输出就可以，不用加0，如N=3，时输出5。

输入格式  
一个整数N（1<=N<=1000000），表示墙壁的长。

输出格式  
输出覆盖方法的最后4位，如果不足4位就输出整个答案。

输入输出样例  
输入  
13  
输出  
3465

哇这真的是一个很神奇的题。一开始想了好久不知道该怎么办，然后去看数据:1，2，5......
这好像没什么用 。然后突然发现:5=22+1.也就是说，x[n]=x[n-1]2+x[n-3]
去试了一下，过了！找规律万岁！（？

Code

#include<bits/stdc++.h>
using namespace std;
int x[1000001]={0,1,2,5};
int main()
{
    int a;cin>>a;
    for(int i=4;i<=a;i++)
    {
        x[i]=x[i-1]*2%10000+x[i-3]%10000;
        x[i]%=10000;
    }
    cout<<x[a];
    return 0;   
}