Forbidden Divisor

$dp[i][j]$ を、長さ $i$ の、各要素が $1$ 以上 $M - 1$ 以下の $D$ でない整数で、総和を $M$ で割った余りが $j$ である数列の数とします。

$j$ が $D$ の倍数でないような $dp[i][j]$ は、$i$ が同じならば全て等しいので、$b_i$ とします。

また、$M/D = K$ とし、$dp[i][kD] = a_{i, k}$ $(0\leq k < K)$ とします。

$a, b$ についての漸化式は、

$\begin{pmatrix} a_{i + 1, 0}\\ a_{i + 1, 1}\\ a_{i + 1, 2}\\ \vdots\\ a_{i + 1, K - 2}\\ a_{i + 1, K - 1}\\ b_{i + 1} \end{pmatrix} = \begin{pmatrix} 0& 1& 1& 1& \ldots& 1& 1& 1& 0& M-K\\ 0& 0& 1& 1& \ldots& 1& 1& 1& 1& M-K\\ 1& 0& 0& 1& \ldots& 1& 1& 1& 1& M-K\\ \vdots& \vdots& \vdots& \vdots& \ddots& \vdots& \vdots& \vdots& \vdots& \vdots\\ 1& 1& 1& 1& \ldots& 1& 0& 0& 1& M-K\\ 1& 1& 1& 1& \ldots& 1& 1& 0& 0& M-K\\ 1& 1& 1& 1& \ldots& 1& 1& 1& 1& M-K-2 \end{pmatrix} \begin{pmatrix} a_{i, 0}\\ a_{i, 1}\\ a_{i, 2}\\ \vdots\\ a_{i, K - 2}\\ a_{i, K - 1}\\ b_{i} \end{pmatrix}$

なので、

$\begin{pmatrix} a_{N, 0}\\ a_{N, 1}\\ a_{N, 2}\\ \vdots\\ a_{N, K - 2}\\ a_{N, K - 1}\\ b_{N} \end{pmatrix} = \begin{pmatrix} 0& 1& 1& 1& \ldots& 1& 1& 1& 0& M-K\\ 0& 0& 1& 1& \ldots& 1& 1& 1& 1& M-K\\ 1& 0& 0& 1& \ldots& 1& 1& 1& 1& M-K\\ \vdots& \vdots& \vdots& \vdots& \ddots& \vdots& \vdots& \vdots& \vdots& \vdots\\ 1& 1& 1& 1& \ldots& 1& 0& 0& 1& M-K\\ 1& 1& 1& 1& \ldots& 1& 1& 0& 0& M-K\\ 1& 1& 1& 1& \ldots& 1& 1& 1& 1& M-K-2 \end{pmatrix}^N \begin{pmatrix} 1\\ 0\\ 0\\ \vdots\\ 0\\ 0\\ 0 \end{pmatrix}$

であり、係数行列は $K + 1$ 次の正方行列なので、繰り返し二乗法によって、答えである $a_{N, 0}$ は時間計算量 $\displaystyle O\left(\left(\frac{M}{D}\right)^3 \log N\right)$ で計算することができます。