解説

変更クエリなしで解くことから考えてみましょう。

dp[i] := i番目までみたときの $a$ と $b$ の組み合わせ

とすると、 $a$ と $b$ の各桁の和はせいぜい $9 + 9 = 18$ であることから、2桁のみ考えたらいいことがわかります。

よって、s[i]となる組み合わせを $c _ {1}$ 、s[i-1]s[i]の2桁となる組み合わせを $c _ {2}$ とすると

$dp[i] = c _ {1} * dp[i - 1] + c _ {2} * dp[i - 2]$

です。

これをよく見てみると、

f:id:jupiro:20200713070100p:plain

となり、行列の演算になっています。

これはセグ木に乗るので、各クエリに対してこの問題は解けました。

定数倍のコツとして、セグ木に行列のを乗せる際はstd::vectorよりもstd::arrayのほうがいいです。

全体取得なので、一番上のところだけみるようにするのもいいです。

提出コード