上海移动网站建设,湖南注册公司,公司网站备案需要多久,建一个论坛网站怎么建题目描述 Description 你可能听说过的Fibonacci数和圆周率Pi。 如果你让这两个概念合并#xff0c;一个新的深奥的概念应运而生#xff1a;Pibonacci数。 这些数可以被定义为对于x0#xff1a; 如果0x4#xff0c;则P(x) 1 …题目描述 Description 你可能听说过的Fibonacci数和圆周率Pi。 如果你让这两个概念合并一个新的深奥的概念应运而生Pibonacci数。 这些数可以被定义为对于x0 如果0x4则P(x) 1 如果4x则P(x) P(x - 1) P(x - pi) 其中Pi 3.1415926535897...在这个问题中你被要求计算对于一个给定的非负整数x对应P(x)的值。输入描述 Input Description 一个非负整数x。输出描述 Output Description 一个正整数P(x)。样例输入 Sample Input 11样例输出 Sample Output 20数据范围及提示 Data Size Hint 数据范围 x30000 来源 ICPC 2001 F 好题啊 转化题意给你一个数你可以一次减去1或者减去pi求你有多少种方法把它减到4如果它本来就小于4方案就是1种 想法1 枚举1的个数算出pi的个数这是pi结尾的算组合数 枚举pi的个数算出1的个数这是1结尾的算组合数 然后加起来 眼瞎以为只有3000高兴地交上去RE了我靠竟然有30000怎么办呢 问了问VFleaking他想了想帮我找出了一个有巨大优化空间的地方 我求组合数是暴力求的其实枚举的时候组合数的nm都是比较接近的所以记一个lastn和一个lastm每次只要乘几个除几个就行了 然后优化到了10000左右可以过又卡住了 FVleaking找到了差不多的题http://acm.hit.edu.cn/hoj/problem/view?id1385 范围是3000多组数据我就交了AC了于是我的信心倍增但是还是不知道怎么过30000 然后下了一个CAC代码当时也只有C和C的 看了以后果然是常数比我好 直接枚举pi的个数为n 然后给剩下的空间加上一个pi算出这个空间可以容下多少个1个数为m 可以想象加上一个pipi的个数还是原来枚举的那么多因为这个空间加上这些pi和1肯定还没满 所以讨论1摆放情况因为有可能1结尾但是超出范围根本不需要这个1但是没关系这个方案只计算了一次也只会计算这一次所以方案数就是C(nm,n) 然后加上前面那个优化就可以AC了.......... 1 const2 h100000000000000;3 type4 aaarray[0..10000]of int64;5 var6 a,b:aa;7 n:longint;8 9 procedure cheng(x:longint);10 var11 i:longint;12 begin13 for i:1 to b[0] do14 b[i]:b[i]*x;15 for i:1 to b[0] do16 begin17 inc(b[i1],b[i]div h);18 b[i]:b[i]mod h;19 end;20 i:b[0]1;21 while b[i]0 do22 begin23 inc(b[0]);24 b[i1]:b[i]div h;25 b[i]:b[i]mod h;26 inc(i);27 end;28 end;29 30 procedure jia;31 var32 i:longint;33 begin34 for i:1 to b[0] do35 inc(a[i],b[i]);36 if b[0]a[0] then a[0]:b[0];37 for i:1 to a[0] do38 begin39 inc(a[i1],a[i]div h);40 a[i]:a[i]mod h;41 end;42 i:a[0]1;43 while a[i]0 do44 begin45 inc(a[0]);46 inc(a[i1],a[i]div h);47 a[i]:a[i]mod h;48 inc(i);49 end;50 end;51 52 procedure chu(x:longint);53 var54 i:longint;55 begin56 for i:b[0] downto 2 do57 begin58 inc(b[i-1],(b[i]mod x)*h);59 b[i]:b[i]div x;60 end;61 b[1]:b[1]div x;62 while (b[b[0]]0)and(b[0]1) do63 dec(b[0]);64 end;65 66 procedure print;67 var68 i:longint;69 k:int64;70 begin71 write(a[a[0]]);72 for i:a[0]-1 downto 1 do73 begin74 k:h div 10;75 while k1 do76 begin77 if a[i]k then write(0);78 k:k div 10;79 end;80 write(a[i]);81 end;82 end;83 84 procedure main;85 var86 i,j,k,last:longint;87 begin88 read(n);89 if n4 then90 begin91 write(1);92 halt;93 end;94 dec(n,4);95 a[0]:1;96 a[1]:1;97 i:0;98 b[0]:1;99 b[1]:1;
100 i:1;
101 j:trunc(npi);
102 while itrunc((npi)/pi) do
103 begin
104 last:j;
105 j:trunc(npi-i*pi);
106 for k:last-1 downto j1 do
107 begin
108 cheng(k1);
109 chu(ik);
110 end;
111 cheng(j1);
112 chu(i);
113 inc(i);
114 jia;
115 end;
116 print;
117 end;
118
119 begin
120 main;
121 end. View Code 转载于:https://www.cnblogs.com/Randolph87/p/3599458.html
