1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2609 Solved: 1450
[Submit][Status]
Description
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
Input
第一行有1个正整数n。
Output
将编程计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
HINT
Source
题解：这道题可以采用“打表—找规律”战术——通过打表可以发现1，5，16，45，121，320，841，2205。。。。然后奇数项1=12,16=42,121=112,841=292,得到另一个序列——1、4、11、29，且11=3×4-1，29=3×11-4，即A1=1,A2=4,Ai=3*Ai-1-Ai-2,所以奇数项规律Finished。。。然后偶数项，将数字除以5，得到1=12，9=32，64=82，规律和上面的一样，只不过A2不一样，然后别的没了，直接高精度。。。（呵呵0ms Accept我也是醉了，代码略长求不鄙视TT）
var
i,j,k,l,m,n:longint;
a,b,c:array[..] of longint;
begin
readln(n);
if odd(n) then
begin
n:=(n+) div ;
if n<= then
begin
if n= then writeln() else writeln();
end
else
begin
a[]:=;
a[]:=;
b[]:=;
b[]:=;
for i:= to n do
begin
if odd(i) then
begin
k:=;
c[]:=b[]+;
for j:= to c[] do
begin
k:=k+b[j]*;
c[j]:=k mod ;
k:=k div ;
end;
for j:= to c[] do
begin
c[j]:=c[j]-a[j];
if c[j]< then
begin
dec(c[j+]);
c[j]:=c[j]+;
end;
end;
while c[c[]]= do dec(c[]);
a[]:=c[];
for j:= to a[] do
a[j]:=c[j];
end
else
begin
k:=;
c[]:=a[]+;
for j:= to c[] do
begin
k:=k+a[j]*;
c[j]:=k mod ;
k:=k div ;
end;
for j:= to c[] do
begin
c[j]:=c[j]-b[j];
if c[j]< then
begin
dec(c[j+]);
c[j]:=c[j]+;
end;
end;
while c[c[]]= do dec(c[]);
b[]:=c[];
for j:= to b[] do
b[j]:=c[j];
end;
end;
if odd(n) then
begin
c[]:=a[];
for i:=a[] downto do
c[i]:=a[i];
end
else
begin
c[]:=c[];
for i:=b[] downto do
c[i]:=b[i];
end;
fillchar(a,sizeof(a),);
a[]:=c[]*;
for i:= to c[] do
begin
for j:= to c[] do
begin
a[i+j-]:=a[i+j-]+c[i]*c[j];
a[i+j]:=a[i+j]+(a[i+j-] div );
a[i+j-]:=a[i+j-] mod ;
end;
end;
while a[a[]]= do dec(a[]);
for i:=a[] downto do
write(a[i]);
writeln;
end;
end
else
begin
n:=n div ;
if n<= then
begin
if n= then writeln() else writeln();
end
else
begin
a[]:=;
a[]:=;
b[]:=;
b[]:=;
for i:= to n do
begin
if odd(i) then
begin
k:=;
c[]:=b[]+; for j:= to c[] do
begin
k:=k+b[j]*;
c[j]:=k mod ;
k:=k div ;
end;
for j:= to c[] do
begin
c[j]:=c[j]-a[j];
if c[j]< then
begin
dec(c[j+]);
c[j]:=c[j]+;
end;
end;
while c[c[]]= do dec(c[]);
a[]:=c[];
for j:= to a[] do
a[j]:=c[j];
end
else
begin
k:=;
c[]:=a[]+; for j:= to c[] do
begin
k:=k+a[j]*;
c[j]:=k mod ;
k:=k div ;
end;
for j:= to c[] do
begin
c[j]:=c[j]-b[j];
if c[j]< then
begin
dec(c[j+]);
c[j]:=c[j]+;
end;
end;
while c[c[]]= do dec(c[]);
b[]:=c[];
for j:= to b[] do
b[j]:=c[j];
end;
end;
if odd(n) then
begin
c[]:=a[];
for i:= to c[] do
c[i]:=a[i];
end
else
begin
c[]:=b[];
for i:= to c[] do
c[i]:=b[i];
end;
fillchar(a,sizeof(a),);
a[]:=*C[];
for i:= to c[] do
for j:= to c[] do
begin
a[i+j-]:=a[i+j-]+c[i]*c[j];
a[i+j]:=a[i+j]+(a[i+j-] div );
a[i+j-]:=a[i+j-] mod ;
end;
while a[a[]]= do dec(a[]);
k:=;
for i:= to a[] do
begin
k:=k+a[i]*;
a[i]:=k mod ;
k:=k div ;
end;
while k> do
begin
inc(a[]);
a[a[]]:=k mod ;
k:=k div ;
end;
for i:=a[] downto do
write(a[i]);
writeln;
end;
end;
end.