005 - Restricted Digits（★7）
4点は行列累乗でOK
行列累乗で間に合わないなら何らかのインチキで計算量を落とす必要がある
$ f(i+j) を$ f(i) と$ f(j) から計算できるような場合、ダブリングに持ち込んで$ f(n) を計算できることがある。
今回の場合、$ f(j,k) = j 桁の条件を満たす整数で、\mod Bがkとなるもの とすると、$ f(i+j,10^j k_j+k_i)=f(i,k_i) \times f(j,k_j) というように計算できる。
ダブリング用のテーブルを作成し、$ N の各bitに対応するものを合成すればよい。計算量は$ B^2 \log N。
解説チラ見してAC 初っ端から大分ムズくてびびった
$ 10^{2^i} のテーブル作るときに $B$ではなく 1e9+7 でmodを取っていたのに気付かず2時間溶かした