yukicoder contest 353 （オムニバス）

　Cまで三完。D、解説読んでも難しい気がしたけど、こんなに解かれるんだなぁ。

コンテストへのリンク

No.2017 Mod7 Parade

　解説AC。

　まず、10^x mod 7が6周期だということを押さえておく。そして、mod 7を考えるので、各数字のmod 7も高々7個。

　これを利用して、

・DP[i][j]で、桁数 mod 6がi個、答え mod 7がjとなるものの個数

　というDPを考える。

　下の桁から追加していくとき、その数字を追加するか、しないか、で遷移は二通り。なので、計算量も抑えられている。

　なお、上の桁からやると桁数を覚えなくても解け、計算量も下がる（というツイートを発見）。確かに！

No.2018 X-Y-X

　解説AC。

　かなり賢い解法に思えるが、隣接要素のxor（差）を考えるのは定石の一つだし、そうして帰着した問題を見ると、偶奇で分けて片方反転させるのも定石。

　迷うのは仕方ないけれど、色々試している間に解けるべきだった。

No.2019 Digits Filling for All Substrings

　これは自力でACできた。

　mod 3でDPすればOK。

　No.2017 Mod7 Paradeと似た解法だけど、こっちの方が大分思いつきやすく感じた。コンテストの問題順が、No.2019 Digits Filling for All Substrings→No.2017 Mod7 Paradeとなっていたら、似た解法の応用問題が後に出題されている、という感じで良かったと思うけれど、全体テスターがいないから仕方ないね。