yukicoder No.315 世界のなんとか3.5
問題文
http://yukicoder.me/problems/766
解法
制約からして桁DP。桁DPを知らない人用に「桁DP入門」という記事を書いた。むしろこっちがメインの記事。
次のようなDPが思いつく。
dp[i][j][k][l][m]:=i桁目まで見ていてj,k,l,mであるような数の総数
・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・m: mod Pの値
・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+10 a_1+10^2a_2\quad(\bmod 8)\]
になる。つまり下3桁が8の倍数ならNも8の倍数。80,800の倍数の時も同様に正しいことが示せる。
よってN-6桁目ぐらいまでは、
dp[i][j][k][l]:=i桁目まで見ていてj,k,lであるような数の総数
・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
というDPをして、N-6桁目以降は
dp2[i][j][k][l][m]:=i桁目まで見ていてj,k,l,mであるような数の総数
・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・m: mod Pの値
・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・m: mod Pの値
というDPをすればいい。そもそも6桁もない場合は愚直に計算するか、少しDPの処理を工夫する必要がある。
ひとこと
世界のなんとか3を解くときに下3桁だけ見ることは考えていたので、今回の問題はさほど頭使わずにできた。でもdpテーブルの0 fillし忘れてたのはダメ。
