Description

轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子

和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不

同的3轮状病毒，如下图所示

现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

Input

第一行有1个正整数n

Output

计算出的不同的n轮状病毒数输出

Sample Input

3

Sample Output

16

 

题解：

手推DP转移方式，推了好久依旧特别长。

不明白为什么他们的公式这么短。

 

代码：

1 var 2   i,j,k,l,n,m,x:longint; 3   a:array[0..200,0..1000]of longint; 4   b,c:array[0..1000]of longint; 5 begin 6   readln(n); 7   if n=1 then begin writeln(1); halt; end; 8   if n=2 then 9   a[0,0]:=1; a[0,1]:=1; a[1,0]:=1; a[1,1]:=3;10   a[2,0]:=1; a[2,1]:=8; a[3,0]:=2; a[3,1]:=1; a[3,2]:=2;11   for i:=4 to n-1 do12   begin13     x:=0;14     for j:=1 to a[i-1,0] do15     begin16       a[i,j]:=a[i,j]+5*a[i-1,j]-8*a[i-2,j]+5*a[i-3,j]-a[i-4,j]+x;17       while a[i,j]<0 do begin dec(a[i,j+1]); a[i,j]:=a[i,j]+10; end;18       x:=a[i,j] div 10;19       a[i,j]:=a[i,j] mod 10;20     end;21     while x>0 do begin inc(j); a[i,j]:=x mod 10; x:=x div 10; end;22     a[i,0]:=j;23   end;24   x:=0;25   for i:=1 to a[n-1,0] do26   begin27     a[n-1,i]:=a[n-1,i]*3+x;28     x:=a[n-1,i] div 10;29     a[n-1,i]:=a[n-1,i] mod 10;30   end;31   while x>0 do begin inc(i); a[n-1,i]:=x mod 10; x:=x div 10; end;32   a[n-1,0]:=i;33   x:=0;34   for i:=1 to a[n-2,0] do35   begin36     a[n-2,i]:=a[n-2,i]*2+x;37     if i=1 then a[n-2,i]:=a[n-2,i]+2;38     x:=a[n-2,i] div 10;39     a[n-2,i]:=a[n-2,i] mod 10;40   end;41   while x>0 do begin inc(i); a[n-2,i]:=x mod 10; x:=x div 10; end;42   a[n-2,0]:=i;43   for i:=1 to a[n-1,0] do44   begin45     a[n-1,i]:=a[n-1,i]-a[n-2,i];46     while a[n-1,i]<0 do47     begin48       dec(a[n-1,i+1]); a[n-1,i]:=a[n-1,i]+10;49     end;50   end;51   while a[n-1,a[n-1,0]]=0 do dec(a[n-1,0]);52   for i:=a[n-1,0] downto 1 do write(a[n-1,i]);53   writeln;54 end.