b236: CSAPC'09 聖誕禮物
Tags :
Accepted rate : 53人/62人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-13 07:57

Content

圣诞节就要到了,小皮准备了n 个圣诞礼物,把它挂在一棵特别的圣诞树上。顽皮的小球发现这棵圣诞树相当地特别,它是一棵二元树,所有的礼物都挂在叶子上,而且每一个节点都可以旋转,并将整棵子树左右反过来。如下图来说,旋转了箭头所指的那个节点以后,整棵子树和所有礼物的顺序就会反过来:

 

小球把原本所有叶子上的礼物由左到右编号为1到n ,并且观察它们经过旋转以后的排列状况,以上图为例,小球把结果标记成(3, 2, 1, 4) ,并称呼它为一个礼物序列。顽皮的小球把这个发现告诉小皮 ,他们决定把所有n片叶子的圣诞树都找出来,把所有叶子上挂的礼物由左到右编号为1到n ,然后开始旋转节点,并将所有的礼物序列记录下来。不过由于数量实在是太多了,而且重复的礼物序列太多, 小皮和小球请你帮忙把礼物序列整理整理,并且告诉小皮和小球总共会有多少个不同的礼物序列?注意到并不是所有n元的序列都是礼物序列,例如(3, 1, 4, 2)这个序列,你找不到任何一棵圣诞树可以得到这个序列。

 

Input

输入仅包含一个正整数 n ,代表小皮准备的礼物个数。

Output

请输出总共有多少个 n 个礼物的礼物序列。由于答案可能很大,你只要输出答案除以 1,000,000,000 的余数即可。

Sample Input #1
4
Sample Output #1
22
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
Hint :

占总分至少 20% 的测试资料满足 n <= 5

占总分至少 40% 的测试资料满足 n <= 10

占总分至少 100% 的测试资料满足 n <= 10,000

Tags:
出處:
2009海峽兩岸青少年程式設計競賽黃上恩 [管理者: tmt514(tomato) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」