ABC189F 漸化式を立てると,一見循環してしまう. これを式変形して循環しない形にして計算する. 振り出しに戻るものが厄介. そのときの答えを \(x\) とおいて, \(x\) に関する 1次式とみなす. \(dp_{i} := i\) に居るときの答え(期待値) とする. \(x = dp_{0}\) とおく. \( dp_{i} \) たちを \(x\) の 1次式の状態で dp を計算する. まず,振り出しに戻るマスが存在しない場合を考える. \(dp_{i} = \sum_{j \in [1,M]} dp_{i+j}/M + 1\). これは累積和で求まる. \(s := \su…