No.048 C

$L_i$ の最小値を $D$ とする.

まず, 最初の $D$ 文字は自由に決めていい.

残りの $L_i - L_1$ 文字は回文でなければならない. 以下, $M_i = L_i - L_1$ とする.

異なる $i, j$ について, それぞれの末尾 $M_i, M_j$ 文字は回文であり, さらに $i$ の末尾 $M_i$ 文字と $j$ の末尾 $M_j$ 文字をくっつけたものも回文でなければならない.

ここで長さ $A$ の回文文字列 $S$ と長さ $B$ の回文文字列 $T$ をくっつけたときに回文になるための条件を考える. $A, B$ は入れ替えても一般性を失わないので, $A \leq B$ とする.

$S+T$ は回文であるので, 末尾 $A$ 文字も $S$ でなければならない. 末尾 $A$ 文字が $S$ なので, $T$ の先頭 $S$ 文字は $S$ でなければならず, $S+T$ の先頭 $2A$ 文字は $S+S$ でなければならない.

これを繰り返していくと, $S+T$ の先頭および末尾 $kA$ 文字は $S$ を $k$ 回繰り返したものとなり, 最後に $C = B\ %\ A$ 文字余る. 余った $C$ 文字は $S$ の先頭および末尾でもあるので, これが一致するためには $C$ 文字は回文でなければならない. また, $S$ の先頭 $A-C$ 文字と末尾 $A-C$ 文字も一致する必要があるので, これも回文でなければならない.

また, $C = 0$ の場合は, $A$ が回文であればいい.

これはユークリッドの互除法そのものであり, このことから $S+T$ が回文になるための条件は,

• $S, T$ がそれぞれ周期 $\gcd(A, B)$ の回文の繰り返しであること

となる.

よって, $g = \gcd(M_i)$ とすると, 組み合わせの数は,

$$2^{D+\lceil g/2 \rceil}$$

となる.