Educational Codeforces Round 8 D. Magic Numbers
最初に通した解法、嘘っぽいのにどうして通ったんだろう。
解法
桁 DP で解ける。
- dp[ 上から i 桁目まで確定 ][ b 未満が確定 ][ a 超えが確定 ][ 0 以外を使ったか ][ 上からの桁数の偶奇 ][ mod M ] := この状態に至るパターン数
以下のことに注意したい。
- 0001 と 1 のように、leading zero を認めると上からの桁数の偶奇が異なる場合がある
- D=0 のとき、 00001020 のように leading zero 部では 0 が自由に使える
less フラグと more フラグを使うという手もあることを他人のコードを見て初めて気がついた。よく考えると当たり前だが、less だけの方に慣れすぎてて気が付かなかった。
雑に書いたら TLE したので、遷移元が 0 のときは弾くようにした。
Educational Codeforces Round 8 D. Magic Numbers
more フラグは良い発見だった。