首页 > 代码库 > 1002: [FJOI2007]轮状病毒

1002: [FJOI2007]轮状病毒

 

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)
 
  1 var  2         i,j,k,l,m,n:longint;  3         a,b,c:array[0..1000] of longint;  4 begin  5         readln(n);  6         if odd(n) then  7                 begin  8                         n:=(n+1) div 2;  9                         if n<=2 then 10                                 begin 11                                         if n=1 then writeln(1) else writeln(16); 12                                 end 13                         else 14                                 begin 15                                         a[1]:=1; 16                                         a[0]:=1; 17                                         b[1]:=4; 18                                         b[0]:=1; 19                                         for i:=3 to n do 20                                                 begin 21                                                         if odd(i) then 22                                                                 begin 23                                                                         k:=0; 24                                                                         c[0]:=b[0]+1; 25                                                                         for j:=1 to c[0] do 26                                                                                 begin 27                                                                                         k:=k+b[j]*3; 28                                                                                         c[j]:=k mod 10; 29                                                                                         k:=k div 10; 30                                                                                 end; 31                                                                         for j:=1 to c[0] do 32                                                                                 begin 33                                                                                         c[j]:=c[j]-a[j]; 34                                                                                         if c[j]<0 then 35                                                                                                 begin 36                                                                                                         dec(c[j+1]); 37                                                                                                         c[j]:=c[j]+10; 38                                                                                                 end; 39                                                                                 end; 40                                                                         while c[c[0]]=0 do dec(c[0]); 41                                                                         a[0]:=c[0]; 42                                                                         for j:=1 to a[0] do 43                                                                                 a[j]:=c[j]; 44                                                                 end 45                                                         else 46                                                                 begin 47                                                                         k:=0; 48                                                                         c[0]:=a[0]+1; 49                                                                         for j:=1 to c[0] do 50                                                                                 begin 51                                                                                         k:=k+a[j]*3; 52                                                                                         c[j]:=k mod 10; 53                                                                                         k:=k div 10; 54                                                                                 end; 55                                                                         for j:=1 to c[0] do 56                                                                                 begin 57                                                                                         c[j]:=c[j]-b[j]; 58                                                                                         if c[j]<0 then 59                                                                                                 begin 60                                                                                                         dec(c[j+1]); 61                                                                                                         c[j]:=c[j]+10; 62                                                                                                 end; 63                                                                                 end; 64                                                                         while c[c[0]]=0 do dec(c[0]); 65                                                                         b[0]:=c[0]; 66                                                                         for j:=1 to b[0] do 67                                                                                 b[j]:=c[j]; 68                                                                 end; 69                                                 end; 70                                         if odd(n) then 71                                                 begin 72                                                         c[0]:=a[0]; 73                                                         for i:=a[0] downto 1 do 74                                                                 c[i]:=a[i]; 75                                                 end 76                                         else 77                                                 begin 78                                                         c[0]:=c[0]; 79                                                         for i:=b[0] downto 1 do 80                                                                 c[i]:=b[i]; 81                                                 end; 82                                         fillchar(a,sizeof(a),0); 83                                         a[0]:=c[0]*2; 84                                         for i:=1 to c[0] do 85                                                 begin 86                                                         for j:=1 to c[0] do 87                                                                 begin 88                                                                         a[i+j-1]:=a[i+j-1]+c[i]*c[j]; 89                                                                         a[i+j]:=a[i+j]+(a[i+j-1] div 10); 90                                                                         a[i+j-1]:=a[i+j-1] mod 10; 91                                                                 end; 92                                                 end; 93                                         while a[a[0]]=0 do dec(a[0]); 94                                         for i:=a[0] downto 1 do 95                                                 write(a[i]); 96                                         writeln; 97                                 end; 98                 end 99         else100                 begin101                         n:=n div 2;102                         if n<=2 then103                                 begin104                                         if n=1 then writeln(5) else writeln(45);105                                 end106                         else107                                 begin108                                         a[0]:=1;109                                         a[1]:=1;110                                         b[0]:=1;111                                         b[1]:=3;112                                         for i:=3 to n do113                                                 begin114                                                         if odd(i) then115                                                                 begin116                                                                         k:=0;117                                                                         c[0]:=b[0]+1;118 119                                                                         for j:=1 to c[0] do120                                                                                 begin121                                                                                         k:=k+b[j]*3;122                                                                                         c[j]:=k mod 10;123                                                                                         k:=k div 10;124                                                                                 end;125                                                                         for j:=1 to c[0] do126                                                                                 begin127                                                                                         c[j]:=c[j]-a[j];128                                                                                         if c[j]<0 then129                                                                                                 begin130                                                                                                         dec(c[j+1]);131                                                                                                         c[j]:=c[j]+10;132                                                                                                 end;133                                                                                 end;134                                                                         while c[c[0]]=0 do dec(c[0]);135                                                                         a[0]:=c[0];136                                                                         for j:=1 to a[0] do137                                                                                 a[j]:=c[j];138                                                                 end139                                                         else140                                                                 begin141                                                                         k:=0;142                                                                         c[0]:=a[0]+1;143 144                                                                         for j:=1 to c[0] do145                                                                                 begin146                                                                                         k:=k+a[j]*3;147                                                                                         c[j]:=k mod 10;148                                                                                         k:=k div 10;149                                                                                 end;150                                                                         for j:=1 to c[0] do151                                                                                 begin152                                                                                         c[j]:=c[j]-b[j];153                                                                                         if c[j]<0 then154                                                                                                 begin155                                                                                                         dec(c[j+1]);156                                                                                                         c[j]:=c[j]+10;157                                                                                                 end;158                                                                                 end;159                                                                         while c[c[0]]=0 do dec(c[0]);160                                                                         b[0]:=c[0];161                                                                         for j:=1 to b[0] do162                                                                                 b[j]:=c[j];163                                                                 end;164                                                 end;165                                         if odd(n) then166                                                 begin167                                                         c[0]:=a[0];168                                                         for i:=1 to c[0] do169                                                                 c[i]:=a[i];170                                                 end171                                         else172                                                 begin173                                                         c[0]:=b[0];174                                                         for i:=1 to c[0] do175                                                                 c[i]:=b[i];176                                                 end;177                                         fillchar(a,sizeof(a),0);178                                         a[0]:=2*C[0];179                                         for i:=1 to c[0] do180                                                 for j:=1 to c[0] do181                                                         begin182                                                                 a[i+j-1]:=a[i+j-1]+c[i]*c[j];183                                                                 a[i+j]:=a[i+j]+(a[i+j-1] div 10);184                                                                 a[i+j-1]:=a[i+j-1] mod 10;185                                                         end;186                                         while a[a[0]]=0 do dec(a[0]);187                                         k:=0;188                                         for i:=1 to a[0] do189                                                 begin190                                                         k:=k+a[i]*5;191                                                         a[i]:=k mod 10;192                                                         k:=k div 10;193                                                 end;194                                         while k>0 do195                                                 begin196                                                         inc(a[0]);197                                                         a[a[0]]:=k mod 10;198                                                         k:=k div 10;199                                                 end;200                                         for i:=a[0] downto 1 do201                                                 write(a[i]);202                                         writeln;203                                 end;204                 end;205 end.

 

1002: [FJOI2007]轮状病毒