Sicily 1049. Mondriaan 解题报告

思路：

　　找规律的一道水题。

　　假设长度为n的有f(n)种画法。容易求出f(0)=1,f(1)=2,f(2)=7...

　　找出递推式f(n)=3f(n-1)+f(n-2)-f(n-3)（推导了半节英语课。。。），打好表之后输入输出搞定。

代码：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int MAX=1000001;
 5 int f[MAX];
 6 
 7 int main(){
 8     int testcases,l;
 9     cin>>testcases;
10     f[0]=1;
11     f[1]=2;
12     f[2]=7;
13     for(int i=3;i<MAX;i++)
14         f[i]=(3*f[i-1]+f[i-2]-f[i-3]+10)%10;//Only the last number is useful.
15     while(testcases--){
16         cin>>l;
17         cout<<f[l]<<endl;
18     }
19     return 0;
20 }