No.528

$N$ の桁数を $d$ とする.

まずは $d$ 桁の回文数の数を考える.

そこで $N$ 以下の最大の回文数を求める.

上から $i$ 桁目と下から $i$ 桁目を比較して, 下から $i$ 桁目の方が大きければそのまま下から $i$ 桁目を上から $i$ 桁目の数字にする.

下から $i$ 桁目の方が小さければ下から $i$ 桁目を9にしてその上の桁を1繰り下げる. 繰り下げた結果上から $i$ 桁目より上の桁に影響が出たならその影響が出た桁から再度行う. そうでない場合は $i$ 桁目から再度行う.

これを $\lfloor d/2 \rfloor$ 桁目まで行う.

これで $N$ 以下の最大の回文数が求まる.

$N$ の上位 $\lceil d/2 \rceil$ 桁が決まれば回文数が一意に決まるので, $d$ 桁の回文数は, $N$ の上位 $\lceil d/2 \rceil$ 桁の数を $n$ とすると, $n-10^{\lceil d/2 \rceil-1}+1$ 個になる.

なお, $N = 10^d$ の場合は $d$ 桁の回文数はない.

$e$ 桁 ($e \lt d$) の回文数は上位 $\lceil e/2 \rceil$ 桁が決まればいいので, $10^{\lceil e/2 \rceil} - 10^{\lceil e/2 \rceil-1}$ 個である.

$10^9$ で割った余りは計算式に $10^k$ が出てるので, $k >= 9$ のときにこの値を $10^k$ を $0$ として計算すればいい.

$10^9+7$ で割った余りは, $10^k$ を $10^9+7$ で割った余りをあらかじめ計算しておけばいい.