No.444

同じ旨味を選ぶパターンは後で考えるとして, まずは先頭の $n$ 個から $c$ 個を重複ありで選んだときの相乗効果 $f(c, n)$ を考える.

$c$ 個目に $i$ の旨味を選ぶためには, $c-1$ 個目には $i$ 番以下の旨味を選択している必要があるので,

$$f(c, n) = a_1 f(c-1, 1) + a_2 f(c-1, 2) + \cdots + a_n f(c-1, n)$$

となる. ただし, $f(0, *) = 1$ である.

これは行列表現にすると以下のようになる.

$$x_c = (f(c, 1), f(c, 2), \dots, f(c, n))^T \\ A = \begin{pmatrix} a_1 & 0 & 0 & \cdots & 0 \\ a_1 & a_2 & 0 & \cdots & 0 \\ a_1 & a_2 & a_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ a_1 & a_2 & a_3 & \cdots & a_n \end{pmatrix} \\ x_0 = (1, 1, \dots, 1)^T \\ x_c = Ax_{c-1}$$

よって,

$$x_c = A^c x_0$$

となるので, 行列の累乗は繰り返し2乗法で計算すればいい.

最後に $\sum a_i^c$ を引くのだが, これは $A^c$ の対角成分であるので, あらためて計算する必要はない.