作者babufong (哔哔)
看板puzzle
标题[中译] ProjectEuler 364 Comfortable distance
时间Sun Dec 25 00:08:26 2011
364. Comfortable distance
http://projecteuler.net/problem=364
有 N 个座位排成一排，N 个人依序入座并把座位坐满，但是入座条件如下：
1. 当有某座位的左右两个相邻的座位都没人时，他就坐这里。
2. 当已经没有上述条件的座位时，就退而求其次，挑有一边没有坐人的座位坐下。
3. 当已经没有上述条件的座位时，就挑剩下的座位坐。
使 T(N) 表示为有 N 个人要用上述条件去坐满 N 个座位时的方法数
下列图示表示出 T(4) = 8
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │●│ │→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │ │●│→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │●│ │ │→│ │●│ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │●│ │→│●│ │●│ │→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│●│ │ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│●│ │ │●│→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│ │●│ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
我们可以验证出 T(10) = 61632 而 T(1000) mod 100000007 = 47255094。
请算出 T(1000000) mod 100000007。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 125.224.5.144
2F：→ utomaya:目前只有24人解出来 看样子不是容易的题目呐? 12/25 01:13
3F：推 utomaya:解掉了! 第37名，排列组合的问题!!! 12/25 12:09
4F：→ utomaya:OEIS完全帮不上忙 仅供参考而已 12/25 12:11
5F：推 LPH66:解掉了+1 我是第43名XD 果然只是个看起来吓人的排列组合题 12/25 21:05
6F：→ LPH66:我是直接写出这个数列的显式出来了XDDDDDD 12/25 21:05
7F：→ Favonia:lol 12/28 15:15
8F：推 LPH66:闲聊一下, 第365题竟然正好在台湾时间跨年时开放XD 12/31 01:48
9F：→ babufong:我觉得这很阴险 意图使人难以抢答（误） 12/31 02:06
10F：推 LPH66:很好...它炸了...想说来抢抢看的说 /_\ 01/01 00:10
11F：→ utomaya:今天应该是Easy题，才那麽多人抢，抢到当机 01/01 01:02
12F：→ utomaya:若没猜错的话 出题的难易度有固定pattern,HMEMEMHMEMEMH.. 01/01 01:05
13F：→ utomaya:猜错了? 这次竟然是M(Medium) 01/01 01:23
14F：→ utomaya:果然没猜错 真的是Easy题! 01/01 01:29
15F：推 LPH66:做出来了 XD 第10名 XDDDDD 01/01 01:55
16F：→ LPH66:还好同样类型的题目以前碰过 回想一下就想起来当初怎麽做的 01/01 01:56