mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ yukicoder 問題 No.315 世界のなんとか3.5 - yukicoder 解法 まずよくある桁 DP っぽく考えると, dp[n][big][exist3][mod3][modP] = (n 桁目で元の数が今作ってる数より大きくなっているフラグが big で 3 が数字に含まれているフラグが exist3 で 3 で割った余りが mod3 で P で割った余りが modP であるような場合の数) とすれば良さそうです。が, P の値がまぁまぁ大きいし桁の数も大きいので, これをそのままやると計算量が 10^9 くらいいってしまい死にます。ところが P は8, 80, 800 に限定されています。例えば… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2015%2F12%2F09%2F075005" title="yukicoder No.315 世界のなんとか3.5 - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-12-09 07:50:05 rich https://mayokoex.hatenablog.com/entry/2015/12/09/075005 1.0 100%