题目描述 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了..........
const
h=;
type
aa=array[..]of int64;
var
a,b:aa;
n:longint; procedure cheng(x:longint);
var
i:longint;
begin
for i:= to b[] do
b[i]:=b[i]*x;
for i:= to b[] do
begin
inc(b[i+],b[i]div h);
b[i]:=b[i]mod h;
end;
i:=b[]+;
while b[i]> do
begin
inc(b[]);
b[i+]:=b[i]div h;
b[i]:=b[i]mod h;
inc(i);
end;
end; procedure jia;
var
i:longint;
begin
for i:= to b[] do
inc(a[i],b[i]);
if b[]>a[] then a[]:=b[];
for i:= to a[] do
begin
inc(a[i+],a[i]div h);
a[i]:=a[i]mod h;
end;
i:=a[]+;
while a[i]> do
begin
inc(a[]);
inc(a[i+],a[i]div h);
a[i]:=a[i]mod h;
inc(i);
end;
end; procedure chu(x:longint);
var
i:longint;
begin
for i:=b[] downto do
begin
inc(b[i-],(b[i]mod x)*h);
b[i]:=b[i]div x;
end;
b[]:=b[]div x;
while (b[b[]]=)and(b[]>) do
dec(b[]);
end; procedure print;
var
i:longint;
k:int64;
begin
write(a[a[]]);
for i:=a[]- downto do
begin
k:=h div ;
while k> do
begin
if a[i]<k then write();
k:=k div ;
end;
write(a[i]);
end;
end; procedure main;
var
i,j,k,last:longint;
begin
read(n);
if n< then
begin
write();
halt;
end;
dec(n,);
a[]:=;
a[]:=;
i:=;
b[]:=;
b[]:=;
i:=;
j:=trunc(n+pi);
while i<=trunc((n+pi)/pi) do
begin
last:=j;
j:=trunc(n+pi-i*pi);
for k:=last- downto j+ do
begin
cheng(k+);
chu(i+k);
end;
cheng(j+);
chu(i);
inc(i);
jia;
end;
print;
end; begin
main;
end.