OMC212(E)

　初期状態において同じ数列に含まれている $2$ つの整数（つまり $1 \leq n \leq 256$ を用いて $2n-1 , 2n$ と表される $2$ 整数）を合わせてペアと呼ぶことにする．任意のペアについて，そのペアを含む数列を対象として操作を行うたびにペアの $2$ 数の間にある数の個数が $1, 3, 7, \dots$ 個と増えていく．また数列の長さに着目すれば，そのペアを含む数列は合計で $8$ 回操作の対象になるとわかる．これより，最終的な数列 $T$ ではペアの関係にある $2$ 数の間には $255$ 個の数があるから，$T$ の $1$ 番目から $256$ 番目の数は奇数，残りは偶数であることがわかる．また左から $1$ 番目から $256$ 番目の数が決まれば残りの数も一意に決まるため，$f(1) + f(2) + \cdots + f(256)$ の値を求めてそれを $2$ 倍すればよい．
　$T=(K_0,K_1,\dots,K_{511})$ とおく（問題文とは違い，添字が $0$ から始まることに注意せよ）．最後の操作の直前の状態では長さ $256$ の $2$ つの数列 $$(K_0,K_2,\dots,K_{510})(=T_0),\quad (K_1,K_3,\dots,K_{511})(=T_1)$$ があり，操作における要素の大小関係についての制約から，$K_{2k}\leq K_{2k+1}\ (0\leq k\leq 255)$ が成り立つ．これは次のように表現できる：

• $K_n,K_m$ が長さ $256$ の同じ列に含まれるための必要十分条件は，$n,m$ を二進数表記したとき下 $1$ 桁が一致することである．
• $n\lt m$ かつ $n,m$ を二進数表記したとき下から $1$ 桁目のみが異なるならば $K_n\leq K_m$．

　また $T_0$ が新しく書き込まれる操作において，操作の対象となる $2$ つの数列は $$(K_0,K_4,\dots,K_{508}),\quad (K_2,K_6,\dots,K_{510})$$ であり，操作での制約より $K_{4k}\leq K_{4k+2}\ (0\leq k\leq 127)$ が成り立つ．$T_1$ についても同様に考えれば次を得る：

• $K_n,K_m$ が長さ $128$ の同じ列に含まれるための必要十分条件は，$n,m$ を二進数表記したとき下 $2$ 桁が一致することである．
• $n\lt m$ かつ $n,m$ を二進数表記したとき下から $2$ 桁目のみが異なるならば $K_n\leq K_m$．

　これ以降も同様に考えれば，次の事実を得る：

• $B_n$ を $n$ の二進数表記で下から $i$ 桁目が $1$ となるような非負整数 $i$ 全体の集合とする（例えば $B_{10}=\{2,4\}$）．このとき $B_n\subset B_m$ ならば $K_n\leq K_m$．

具体的には $B_n \subset B_m$ を満たす $n, m$ について「$n$ のある一つの桁のみを選んでその桁を $0$ から $1$ にする」という操作を繰り返すことで $n=m$ にすることができることから $K_n \leq K_m$ が従う．またこの条件を満たすような $T$ であれば，初期状態から適切に操作を繰り返すことで作成可能であることも分かる．
　これを踏まえて，$i=0,1,\dots,255$ に対し $f(i+1)$ を求める．$B_{n}$ の要素数を $c_{n}$ で表すことにすると，$B_n \subsetneq B_{i}$ を満たす $n$ は $2^{c_{i}} - 1$ 個，$B_{i} \subsetneq B_n$ を満たす $n$ は $2^{8-c_{i}} - 1$ 個あることから $2\times(2^{c_{i}}-1) + 1 \leq K_{i-1}\leq 2\times(256-2^{8-{c_{i}}})+1$ が必要である．逆に，これを満たす任意の正の奇数が $K_{i}$ になり得る．従って $f(i+1) = 258-2^{8-c_{i}}-2^{c_{i}}$ が得られた．$c_{i} = k \ ( 0 \leq k \leq 8 )$ を満たす $i \ ( 0 \leq i \leq 255 )$ は $\dbinom{8}{k}$ 個あるため，求めるべき値は $$2 \left( \sum_{k=0}^{8} \ (258-2^{8-k}-2^{k}) × \dbinom{8}{k} \right) = \mathbf{105852}.$$