Editorial
数列のi項目まで決めたとき、i+1項目を決める操作は以下のような式で表すことができます。
- i項目までを10進整数と見たときの値をAi, 次の項をai+1とするとAi+1=10A+ai+1
また、合同式の性質より以下が成り立ちます。
- ある整数a,bについてa≡b(modK)ならば任意の整数cにおいてac≡bc(modK),a+c≡b+c(modK)
このような事実より、i項目まで決めるときにAi−1までをKで割ったあまりだけを見ていけば良いということがわかります。
よって、以下のようなDPテーブルを得ます。
- dp[i][j]=i項目まで決めたときにKで割ったあまりがjとなることはあるか?
また、以下のような遷移式を考えます。
- dp[i][j]=1ならばdp[i+1][(10j+a1)%K], dp[i+1][(10j+a2)%K], ..., dp[i+1][(10j+aM)%K]=1
- dp[i][j]=0ならば何もしない
答えはdp[i][0]=1となる最大のiです。
したがってO(NK)でこの問題が解けました。N,Kは最大でも103と小さいのでNK回の計算でも十分高速です。
ここではDPをしていますが一項前までで作れる数のmodKでの値をsetなどで持っておく、BFS的に実装するというようなことも可能です。
以下にC++での実装例を示していますが、dp[i−1][j]=i(i≥1)項目まで決めたときの...としていることに注意してください。
類題 : ABC240_C - Jumping Takahashi
実装例(C++)