作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 423 Consecutive die throw
时间Mon Apr 15 23:27:21 2013
423. Consecutive die throws
http://projecteuler.net/problem=423
令n为正整数。
将一六面骰重覆骰n次，令c为接连两次骰出同样数字的对数。
例如，如果n = 7然後骰子依序骰出(1, 1, 5, 6, 6, 6, 3)的结果，那我们可以数出以下
几对：
(
1, 1, 5, 6, 6, 6, 3)
(1, 1, 5,
6, 6, 6, 3)
(1, 1, 5, 6,
6, 6, 3)
所以，在(1, 1, 5, 6, 6, 6, 3)这组结果中c = 3。
定义C(n)为将骰子重覆骰n次的所有可能结果中，其c值不超过π(n)（注１）的组数。
例如，C(3) = 216，C(4) = 1290，C(11) = 361912500以及
C(24) = 4727547363281250000。
定义S(L)为ΣC(n)对1 ≦ n ≦ L的和。
例如，S(50) mod 1000000007 = 832833871。
请求出S(50000000) mod 1000000007。
（注１）在这里的π指的是质数计数函数，即π(n)代表有多少质数≦ n。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.2.129.163