No.303

$L = 2$ のときは特別扱いで, 長さ $1$ のブロックを1つ買い, うち1つを長さ $\alpha, 1-\alpha$ に分割して $\alpha, 1, 1-\alpha$ の順に並べる. よってコストは $3$ で, 組み合わせは無限大である.

$L$ が奇数のときは, 長さ $L$ のブロックを買えば $L$ 円なので, 最小のコストは $L$ 円である.

$L$ が偶数のときは, 長さ $L - 1$ のブロックと長さ $1$ のブロックを買えば $L$ 円なので最小コストは $L$ 円である.

よってどちらも最小コストは $L$ 円であり, ブロックの分割は考えなくていい.

長さ $x$ の塀を作るブロックの並び (真ん中に切れ目があってもいい) の組み合わせの数を $A(x)$ とすると, 左端に長さ $2k+1$ の長さのブロックを置いたときの残りの部分の組み合わせの数は $A(x-1-2k)$ なので,

$$A(x) = \sum A(x-1-2k)$$

s.t.

$$A(0) = A(1) = 1$$

となる. $S(x) = \sum A(x-2k)$ とすると,

$$A(x) = S(x-1) \\ S(x) = S(x-2) + A(x)$$

となるので, これを整理して,

$$S(x) = S(x-1) + S(x-2)$$

となる. これはフィボナッチ数列である.

大きな数のフィボナッチ数列は行列を使った繰り返し2乗法で高速化する.

しかし, 計算結果が非常に大きくなる ($10^{10^5}$ 以上) ので, BigInt では遅すぎてこれでも TLE してしまう.

そこで禁断の手ではある (環境に依存してしまう) が, GMP を使って計算を高速化することで TLE を避ける.

なお, $L$ が偶数のときは, 真ん中に切れ目があるブロックの並びの組み合わせの数 $A(L/2)^2$ を引く.