CodeChef June Challenge 2018の問題: Expected Buildings (Code: BUILDIT)
問題ページ: https://www.codechef.com/JUNE18A/problems/BUILDIT
問題概要
1つの円があり、円の中心にChefが立っている。
この円を周囲は個の区間に分割され、各区間に1, 2, ..., hと時計回りに番号が付けられている。そこに個の建物が存在し、番目の建物は区間内に含まれている。
また、円の中心に立っているChefの視界範囲はであり、円の周囲の連続した個の区間を一度に見ることができる。
今回、Chefが向く方向をランダムに決定する。
各についてが決められており、視界に(mod )が含まれる確率は()である。
ただし、がでかいため、は最初の個しか与えられず、については係数を用いて以下の式で計算できる。
ランダムな方向を向いた時のChefの視界の範囲に含まれる建物の数の期待値をmodulo 163577857で求めなさい。