Posts

持っていなかったのでケチった

入青しました

1/6 のコンテストにて、2019 年から実に 4 年半以上の月日をかけて入青しました。

うぇーい

せっかくブログを立てたので競プロの記事を書きます。

dp などの問題で確率 mod P (P は大きい素数)を求めることがしばしばあります。
初見だと「は？確率の mod？何いってんだこいつ」となりがちなので、この記事では

単純なナップサック dp のような D 問題相当の dp なら解けるけど、確率 mod P とか言われると「は？何いってんだこいつ」となる人向けに

0. Python ユーザーが ACL の modint に相当するライブラリ等を使わずに
1. 答えが小数になることを許容してそのまま実装し
2. 実装した確率 dp を機械的に mod P に対応させる

というステップで解く方法について整理しました。