3150 Pibonacci数 - Wikioi

题目描述 Description

    　　你可能听说过的Fibonacci数和圆周率Pi。

    　　如果你让这两个概念合并，一个新的深奥的概念应运而生：Pibonacci数。

    　　这些数可以被定义为对于x>=0：

    　　　　如果0<=x<4，则P(x) = 1

    　　　　如果4<=x，则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

    数据范围 x<=30000

     

    来源 ICPC 2001 F

 

好题啊

转化题意，给你一个数，你可以一次减去1，或者减去pi，求你有多少种方法把它减到<4（如果它本来就小于4，方案就是1种）

想法1

枚举1的个数算出pi的个数，这是pi结尾的，算组合数

枚举pi的个数算出1的个数这是1结尾的，算组合数

然后加起来

眼瞎，以为只有3000，高兴地交上去，RE了，我靠竟然有30000，怎么办呢

问了问VFleaking，他想了想，帮我找出了一个有巨大优化空间的地方

我求组合数是暴力求的，其实枚举的时候组合数的n，m都是比较接近的，所以记一个lastn和一个lastm每次只要乘几个除几个就行了

然后优化到了10000左右可以过，又卡住了

FVleaking找到了差不多的题http://acm.hit.edu.cn/hoj/problem/view?id=1385

范围是3000，多组数据，我就交了，AC了，于是我的信心倍增，但是还是不知道怎么过30000

然后下了一个C++AC代码（当时也只有C和C++的）

看了以后果然是常数比我好

直接枚举pi的个数为n

然后给剩下的空间加上一个pi，算出这个空间可以容下多少个1，个数为m

可以想象，加上一个pi，pi的个数还是原来枚举的那么多（因为这个空间加上这些pi和1肯定还没满）

所以讨论1摆放情况，因为有可能1结尾，但是超出范围，根本不需要这个1，但是没关系这个方案只计算了一次也只会计算这一次，所以方案数就是C(n+m,n)

然后加上前面那个优化，就可以AC了..........

 

1 const 2 h=100000000000000; 3 type 4 aa=array[0..10000]of int64; 5 var 6 a,b:aa; 7 n:longint; 8 9 procedure cheng(x:longint); 10 var 11 i:longint; 12 begin 13 for i:=1 to b[0] do 14 b[i]:=b[i]*x; 15 for i:=1 to b[0] do 16 begin 17 inc(b[i+1],b[i]div h); 18 b[i]:=b[i]mod h; 19 end; 20 i:=b[0]+1; 21 while b[i]>0 do 22 begin 23 inc(b[0]); 24 b[i+1]:=b[i]div h; 25 b[i]:=b[i]mod h; 26 inc(i); 27 end; 28 end; 29 30 procedure jia; 31 var 32 i:longint; 33 begin 34 for i:=1 to b[0] do 35 inc(a[i],b[i]); 36 if b[0]>a[0] then a[0]:=b[0]; 37 for i:=1 to a[0] do 38 begin 39 inc(a[i+1],a[i]div h); 40 a[i]:=a[i]mod h; 41 end; 42 i:=a[0]+1; 43 while a[i]>0 do 44 begin 45 inc(a[0]); 46 inc(a[i+1],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 var 54 i:longint; 55 begin 56 for i:=b[0] downto 2 do 57 begin 58 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) do 63 dec(b[0]); 64 end; 65 66 procedure print; 67 var 68 i:longint; 69 k:int64; 70 begin 71 write(a[a[0]]); 72 for i:=a[0]-1 downto 1 do 73 begin 74 k:=h div 10; 75 while k>1 do 76 begin 77 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 var 86 i,j,k,last:longint; 87 begin 88 read(n); 89 if n<4 then 90 begin 91 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(n+pi); 102 while i<=trunc((n+pi)/pi) do 103 begin 104 last:=j; 105 j:=trunc(n+pi-i*pi); 106 for k:=last-1 downto j+1 do 107 begin 108 cheng(k+1); 109 chu(i+k); 110 end; 111 cheng(j+1); 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

总结

以上是生活随笔为你收集整理的3150 Pibonacci数 - Wikioi的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。