首页 > 代码库 > 1002: [FJOI2007]轮状病毒
1002: [FJOI2007]轮状病毒
1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 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]轮状病毒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。