题目描述 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了..........
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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.