解説
変更クエリなしで解くことから考えてみましょう。
dp[i] := i番目までみたときのと
の組み合わせ
とすると、と
の各桁の和はせいぜい
であることから、2桁のみ考えたらいいことがわかります。
よって、s[i]となる組み合わせを、s[i-1]s[i]の2桁となる組み合わせを
とすると
です。
これをよく見てみると、
となり、行列の演算になっています。
これはセグ木に乗るので、各クエリに対してこの問題は解けました。
定数倍のコツとして、セグ木に行列のを乗せる際はstd::vectorよりもstd::arrayのほうがいいです。
全体取得なので、一番上のところだけみるようにするのもいいです。
