[中譯] ProjectEuler 364 Comfortable distance

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者babufong (嗶嗶)時間14年前 (2011/12/25 00:08)推噓6(6推 0噓 10→)

留言16則, 4人參與討論串1/1

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