Official

D - Digits of Prefix Product Editorial by miscalculation53

writer 解

\(a_i = 10^{2^{i-1}} - 1 = \underbrace{99\dots 99}_{2^{i-1} \ 個} \ (i \geq 1)\) と定めると、任意の \(k \geq 1\) に対し \(b_k = \displaystyle \prod_{i=1}^k a_i\) は同じ桁が隣り合いません。

証明:\(b_k = \displaystyle \prod_{i=1}^k \left(10^{2^{i-1}} - 1\right) = \sum_{j=0}^{2^{k-1}} (-1)^{\mathrm{popcount}(j) + 1} \cdot 10^j\) となります。一般に、\(\displaystyle \sum_{j = 0}^n c_j \cdot 10^j \ (c_j \in \{1, -1\})\) の十進表記は、列 \((c_0, \dots, c_n)\) のランレングス圧縮をもとに次のように計算されます:

  11..11        11..11         ... 
-)       11..11        11..11  ...
----------------------------------
  10..00 88..89 10..00 88..89  ...

ここで、popcount の偶奇の列 (Thue–Morse sequence) において同じ値が \(3\) 連続しない(つまり、ランレングス圧縮した際の連の長さが \(2\) 以下である)ことより、\(b_k\) において同じ桁が隣り合わないことが従います。\(\square\)


元の問題に戻ります。\(2\) 個目の条件を満たすために、先頭のいくつかの \(a_i\) をまとめておけばよいです。この掛け算の結果は \(0\) の桁を含みますが、上の議論での \(b_k\) の十進表記の形より、\(2\) 倍(\(3\) 倍や \(4\) 倍などでもよいです)しておけば、他の条件を満たしたまま \(0\) の桁を含まなくなることがわかります。

結局、次のように定められる \(a_1, \dots, a_{10}\) が条件を満たします:

\(\begin{aligned} a_1 &= 2 \times 9 \times 99 \times 9999 \times \cdots \times \underbrace{99\dots99}_{64\ 個} && (128\ 桁), \\ a_2 &= \underbrace{99\dots\dots99}_{128\ 個} && (128\ 桁), \\ a_3 &= \underbrace{99\dots\dots\dots99}_{256\ 個} && (256\ 桁), \\ &\vdots \\ a_{10} &= \underbrace{99\dots\dots\dots\dots99}_{32768\ 個} && (32768\ 桁). \end{aligned}\)

桁数の合計は \(65536\) 桁です。

posted:
last update: