[中译] ProjectEuler 502 Counting Castles

楼主: tml (流刑人形)   2015-02-14 03:45:21
502. Counting Castles
https://projecteuler.net/problem=502
我们定义一个石块为一高度为1且宽度为正整数的长方形,并定义一个城堡为一堆石块
堆叠起来的一种结构。
给定一高度为h且宽度为w的铅直棋盘方格,我们可以依以下规则来构造城堡:
1. 石块可以堆叠在其他石块之上,但是不能突出下面石块的边界或架在多个石块之上。
2. 所有石块都和棋盘方格对齐。
3. 在同一高度的任两石块至少间隔一个空格。
4. 最下层必为一宽度为w的石块。
5. 城堡最高点的高度恰为h。
6. 城堡必须由偶数个石块组成。
下图为w = 8、h = 5时的一个城堡的范例:
https://projecteuler.net/project/images/p502_castles.png
令F(w, h)为给定棋盘宽度w和高度h后,所有可构造出的城堡的数目。
例如,F(4, 2) = 10、F(13, 10) = 3729050610636、F(10, 13) = 37959702514以及
   F(100,100) mod 1000000007 = 841913936。
请求出F(10^12, 100) + F(10000, 10000) + F(100, 10^12) mod 1000000007。

Links booklink

Contact Us: admin [ a t ] ucptt.com