エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
yukicoder No.315 世界のなんとか3.5 - pekempey's blog
記事へのコメント0件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
yukicoder No.315 世界のなんとか3.5 - pekempey's blog
問題文 http://yukicoder.me/problems/766 解法 制約からして桁DP。桁DPを知らない人用に「桁DP入門」と... 問題文 http://yukicoder.me/problems/766 解法 制約からして桁DP。桁DPを知らない人用に「桁DP入門」という記事を書いた。むしろこっちがメインの記事。 pekempey.hatenablog.com 次のようなDPが思いつく。 dp[i][j][k][l][m]:=i桁目まで見ていてj,k,l,mであるような数の総数 ・j: A未満であることが確定 ・k: mod 3の値 ・l: すでに3を選んでいる ・m: mod Pの値 しかしこれでは状態数がヤバイ。そこで次のようなmod Pの性質を使う。 下3桁が8の倍数なら8の倍数になる 下4桁が80の倍数なら80の倍数になる 下5桁が800の倍数なら800の倍数になる \[N=a_0+10 a_1+10^2a_2+10^3a_3\cdots\] と展開してmod 8を取ってみれば、 \[N \equiv a_0