No.213

素数サイコロだけを $P$ 個振ったときに出る目の合計が $i$ となる組み合わせの数 $C_p(i)$ と合成数サイコロだけを $C$ 個振ったときに出る目の合計が $j$ となる組み合わせの数 $C_c(j)$ をそれぞれ全探索で求める.

このとき, すべてのサイコロを振ったときに出る目の合計が $k$ となる組み合わせの数を $C(k)$ とすると,

$$C(i+j) \leftarrow C_p(i)C_c(j)$$

で計算できる. $k$ は最大 $M = 13P + 12C$ である.

さて, すごろくで $n$ のマスに到達する組み合わせの数を $A(n)$ とする. ただし, ゴールを超えたマスも対象する. このとき,

$$A(n) = \sum_k C(k)A(n-k) \ (0 \leq n-k \lt N)$$

s.t.

$$A(0) = 1$$

となる. これを順に計算すればいいのだが, $N$ が大きいので愚直に計算すると間に合わない.

そこで, コンパニオン行列を使う.

$$\left( \begin{array}{c} A(n+1) \\ A(n) \\ A(n-1) \\ A(n-2) \\ \vdots \\ A(n-M+2) \end{array} \right) = \left( \begin{array}{cccccc} C(1) & C(2) & C(3) & \cdots & C(M-1)& C(M) \\ 1 & & & & & \\ & 1 & & & & \\ & & 1 & & & \\ & & & \ddots & & \\ & & & & 1 & \\ \end{array} \right) \left( \begin{array}{c} A(n) \\ A(n-1) \\ A(n-2) \\ A(n-3) \\ \vdots \\ A(n-M+1) \end{array} \right)$$

となるので, $A(1) \dots A(M)$ は愚直に計算し, $A(M+1) \dots A(N)$ はコンパニオン行列の累乗を繰り返し2乗法で計算し, $A(N) \dots A(N+M-1)$ は愚直に計算する.

$A(N) \dots A(N+M-1)$ の和が答えとなる.

…という方法だと計算量が $O(M^3 \log N)$ となり, 微妙に間に合わなかった.

そこで, まず $A(N) \dots A(N+M-1)$ の和を求めるのを $A(N)$ だけ求めればいいようにする.

これは, $0$ から進む方向で考えるのではなく, $N \dots N+M-1$ から戻る方向で考えて $0$ に到達する組み合わせの数を考えればいい. ただし, $N+c$ の位置から1手目は $N$ 未満にたどり着かなくてはならない.

そして, $A(n)$ を $n$ マス進んだときの組み合わせの数ではなく, 残り $n$ マスの地点にたどり着く組み合わせの数と考えれば,

$$A(n) = \sum_k C(k)A(n-k)$$

s.t.

$$A(n) = 1 \ (n \leq 0)$$

となる.

$N \leq M$ のときはこれを愚直に計算し, $N \gt M$ のときは $A(1) \dots A(M)$ を愚直に計算し, あとはきたまさ法で計算すれば, 計算量は $O(M^2 \log M)$ となる.