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:
