E - Super Lucky Sequence

2 secs 1024 MB
Yourein

Editorial


数列の項目まで決めたとき、項目を決める操作は以下のような式で表すことができます。

  • 項目までを10進整数と見たときの値を, 次の項をとすると

また、合同式の性質より以下が成り立ちます。

  • ある整数についてならば任意の整数において

このような事実より、項目まで決めるときにまでをで割ったあまりだけを見ていけば良いということがわかります。
よって、以下のようなDPテーブルを得ます。

  • 項目まで決めたときにで割ったあまりがとなることはあるか?

また、以下のような遷移式を考えます。

  • ならば
  • ならば何もしない

答えはとなる最大のです。

したがってでこの問題が解けました。は最大でもと小さいので回の計算でも十分高速です。

ここではDPをしていますが一項前までで作れる数のでの値をsetなどで持っておく、BFS的に実装するというようなことも可能です。
以下にC++での実装例を示していますが、項目まで決めたときの...としていることに注意してください。

類題 : ABC240_C - Jumping Takahashi

実装例(C++)