概要
想定解法よりも計算量が落ちたようなので、一応書いておきます。$O(R\log R)$ 時間で解けます。
解法
$a$ を $1$ 個以上 $k=A_a$ 個以下並べたものを、「ブロック」と呼ぶことにします。
数列を作る方法は、
- ブロックを並べる方法
- ただし、同じ $a$ に対応するブロックの隣接は許さない
と対応します。これを包除原理で処理します。
包除で条件に違反すると決め打った部分をまとめて「新しいブロック」を作ります。同じ $a$ に対応するブロックを $n$ 個並べたものを重み $(-1)^{n-1}$ の「新しいブロック」として、制約なく「新しいブロック」を並べる問題を解けばよいです。
種類 $a$ に対応する「ブロック」の母関数：$f_a = \sum_{i=1}^{k}x^{ai}$
種類 $a$ に対応する「新しいブロック」の母関数：$F_a = \sum_{n=1}^{\infty}(-1)^{n-1}f_a^n = \frac{f_a}{1+f_a}$
「新しいブロック」の母関数：$F = \sum_{a} F_a$
答の母関数：$\frac{1}{1-F}$
となります。簡単な計算で $F_a = \frac{x^k-x^{(a+1)k}}{1-x^{(a+1)k}}$ であることが分かります。これは連続する $(a+1)k$ 項の中に $2$ つしか $0$ でない係数を持たない形式的べき級数です。よって $F$ の $R$ 次以下の部分は $O(R\log R)$ 時間で計算できます。最後に形式的べき級数逆元をとる計算も含め、全ての計算を $O(R\log R)$ 時間で行うことができます。
参考
この問題のときに話題になっていた解法と同じ計算方法です。
