ProjectEuler 316 Numbers in decimal expansions - 拼圖

ProjectEuler 第316題 [Numbers in decimal expansions]

http://projecteuler.net/index.php?section=problems&id=316

令P=P_1P_2P_3....為一個由數字組成的無限序列, 每一個數字是從 {0,1,2,3,4,5,6,7,8,
9} 集合中以均等的機率選出來的

很顯然的，p等同於以0開頭的實數，0.P_1P_2P_3....
而且我們可以知道，從[0,1)區間任選一個實數，就等同於 從{0,1,2,3,4,5,6,7,8,9}
集合中以均等的機率選擇一個隨機數字所組成的無限序列

對於任何有d位數的正整數n，令k代表n在任意隨機數列中第一次出現的位置
令g(n)為k的期望值，我們可以證實g(n)永遠是有限的，而且有趣的是，永遠是整數

例如，n=535
p = 31415926535897...., k = 9
p = 355287143650049560000490848764084685354..., k = 36

我們可以發現 g(535)=1008

│ 10^6│
999 │ ___ │
你被告知 Σ g(│ n │) = 27280188
n=2 └ ┘

│10^16│
999999 │ ___ │
試求 Σ g(│ n │) = ?
n=2 └ ┘

註:│x│代表對x做無條件捨去的運算
└ ┘

--
鋪了好長的梗，其實就是丟骰子的問題
假設骰子有10面，分別寫上0~9
g(535)就是一直丟，直到出現連在一起的"535"，要丟幾次的期望值，也就是1010次
再減掉2，因為是first index
所以是1008

--