题解 P1990 【覆盖墙壁】

· · 题解

一道非常经典的递推

公式是 a[ i ]=a[ i-1 ]*2+a[ i-2 ]

但只要输出后四位 所以mod10000 就行了

var a:array[1..1000000]of longint;
i,n:longint;
begin
read(n);
a[1]:=1;
a[2]:=2;
a[3]:=5;
for i:=4 to 1000000 do 
a[i]:=(a[i-1]+a[i-2]*3)mod 10000;
write(a[n]);
end.