*[[Problem 423:http://projecteuler.net/problem=423]] 「連続サイコロ投げ」 [#r71dc171]

ある正の整数を '''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 となる.

一個の六面のサイコロを '''n''' 回投げたとき '''c''' が π('''n''') &sup{1}; を超えない結果の数を C('''n''') と定義しよう.~
例として, C(3) = 216, C(4) = 1290, C(11) = 361912500, そして C(24) = 4727547363281250000.

'''n''' が 1 ≤ '''n''' ≤ '''L''' のときの Σ'''C'''('''n''') を S('''L''') と定義しよう.~
例として, S(50) mod 1 000 000 007 = 832833871.

S(50 000 000) mod 1 000 000 007 を求めよ.

&sup{1}; π は''素数計数関数'' (prime-counting function) を意味する. すなわち, π('''n''') は '''n''' 以下の素数の個数.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS