問題の確認
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 となる.
一個の六面のサイコロを n 回投げたとき c が π(n) 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 を求めよ.
1 π は素数計数関数 (prime-counting function) を意味する. すなわち, π(n) は n 以下の素数の個数.
まず思いついたのは
a[n回目の振り][連続した数]として
a[n][i]=a[n-1][i-1]+5*a[n-1][i]
という漸化式です。
これは１０分で確認できました。
難しいのはここから先です。
実験にn=11として
Σa[i][1](i=１～11)＝Σa[i][0](i=1～10)+Σa[i][0](i=2～10)+,,,+Σa[i][0](i=10)
という関係は見つけていますが高速な実装に落とし込む方法がわからない状態です。
最終更新：2015年12月08日 10:11
