b236.
CSAPC'09 聖誕禮物
內容
圣诞节就要到了，小皮准备了n 个圣诞礼物，把它挂在一棵特别的圣诞树上。顽皮的小球发现这棵圣诞树相当地特别，它是一棵二元树，所有的礼物都挂在叶子上，而且每一个节点都可以旋转，并将整棵子树左右反过来。如下图来说，旋转了箭头所指的那个节点以后，整棵子树和所有礼物的顺序就会反过来：
小球把原本所有叶子上的礼物由左到右编号为1到n ，并且观察它们经过旋转以后的排列状况，以上图为例，小球把结果标记成(3, 2, 1, 4) ，并称呼它为一个礼物序列。顽皮的小球把这个发现告诉小皮 ，他们决定把所有n片叶子的圣诞树都找出来，把所有叶子上挂的礼物由左到右编号为1到n ，然后开始旋转节点，并将所有的礼物序列记录下来。不过由于数量实在是太多了，而且重复的礼物序列太多， 小皮和小球请你帮忙把礼物序列整理整理，并且告诉小皮和小球总共会有多少个不同的礼物序列？注意到并不是所有n元的序列都是礼物序列，例如(3, 1, 4, 2)这个序列，你找不到任何一棵圣诞树可以得到这个序列。
輸入說明
输入仅包含一个正整数 n ，代表小皮准备的礼物个数。
輸出說明
请输出总共有多少个 n 个礼物的礼物序列。由于答案可能很大，你只要输出答案除以 1,000,000,000 的余数即可。
範例輸入
#1
4
範例輸出
#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
不公開 測資點#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
提示 ：
占总分至少 20% 的测试资料满足 n <= 5
占总分至少 40% 的测试资料满足 n <= 10
占总分至少 100% 的测试资料满足 n <= 10,000
標籤:
出處:
2009海峽兩岸青少年程式設計競賽黃上恩
[管理者：
tmt514
(tomato)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||