题解 P2144 【[FJOI2007]轮状病毒】

题解 P2144 【[FJOI2007]轮状病毒】

怎么pascal题解这么少啊，本蒟蒻也来贡献一篇呗~

一看这题，第一想到(打表)找规律，

于是就开心的手推了前几个答案为1 5 16 45 121...

不难发现，奇数项是完全平方数，偶数项是5的倍数，

又可得前两项是1和3的斐波那契数列，于是有了递推式

f[n]=f[n-1]+f[n-2];

F[n]=F[n]^2-(1-n mod 2)*4

当n=100时显然要爆int64，于是要写高精

uses math;
var
a,b,c,d,f:array[0..1000005] of longint;
i,j,n,k,m,la,lb,lc:longint;
procedure jia(p:longint); 斐波那契数列的加法，用2个数组轮换存储，一个d数组临时存储
var
i,j,n,k,m:longint;
begin
fillchar(d,sizeof(d),0);
for i:=1 to max(la,lb) do
begin
d[i]:=d[i]+c[i]+b[i];
d[i+1]:=d[i] div 10;
d[i]:=d[i] mod 10;
end;
if odd(p) then
begin
lb:=lb+d[lb+1];
for i:=1 to lb do c[i]:=d[i];
end
else
begin
la:=la+d[la+1];
for i:=1 to la do b[i]:=d[i];
end;
if (b[la+1]<>0) then inc(la);
if (c[lb+1]<>0) then inc(lb);
lc:=max(la,lb);//d数组的长度是la,lb中的最大的长度
end;
procedure cheng1();//处理cf
var
i,j,n,k,m,x:longint;
begin
fillchar(d,sizeof(d),0);
for i:=1 to la do
begin
x:=0;
for j:=1 to lb do
begin
d[i+j-1]:=c[i]f[j]+x+d[i+j-1];
x:=d[i+j-1] div 10;
d[i+j-1]:=d[i+j-1] mod 10;
end;
d[i+j]:=x;
end;
lc:=la+lb;
while (d[lc]=0)and(lc>1) do dec(lc);
end;
procedure cheng();//处理bf的情况
var
i,j,n,k,m,x:longint;
begin
fillchar(d,sizeof(d),0);//d数组清零
for i:=1 to la do
begin
x:=0;
for j:=1 to lb do
begin
d[i+j-1]:=b[i]f[j]+x+d[i+j-1];
x:=d[i+j-1] div 10;
d[i+j-1]:=d[i+j-1] mod 10;
end;
d[i+j]:=x;
end;
lc:=la+lb;
while (d[lc]=0)and(lc>1) do dec(lc);
end;
procedure jian();//公式得只减4
var
i:longint;
begin
d[1]:=d[1]-4;
for i:=1 to lc do
begin
if d[i]<0 then
begin
d[i]:=d[i]+10;
dec(d[i+1]);
end;
end;
while (d[lc]=0)and(lc>1) do dec(lc);
end;
begin
readln(n);
la:=1;
lb:=1;//la,lb是b,c数组的长度
b[1]:=3;
c[1]:=1;
if n=1 then begin writeln(1); halt; end;
if n=2 then begin writeln(5); halt; end;
//根据推出来的公式，需要特判n=1,2的情况
for i:=3 to n do
begin
if i mod 2=0 then
begin
jia(i);//加法
for j:=1 to lc do f[j]:=b[j];
//f数组是临时数组，暂存值
lb:=lc;
cheng();//乘法
jian();//减法
end else
begin
jia(i);
for j:=1 to lc do f[j]:=c[j];
la:=lc;
cheng1();
end;
end;
for j:=lc downto 1 do write(d[j]);
//输出,因为用了反存，所以要倒序输出
end.