OMC051(F)

　スコアを最大化する $X$ について考える．ある整数 $a$ を十進法表記したとき $a = \overline{a_1a_2 \cdots a_{2021}}$ と表せるとする. さらに $b_i = 9 - a_i$ とすれば，$a \in X$ となるための必要十分条件は $\oplus$ を排他的論理和として $$b_1 \oplus b_2 \oplus \cdots \oplus b_{2021} = 0 \tag{1}$$ となることを示す．スコアの定義より，$S$ の元を大きい方から順に見て，$X$ の元となり得るものを貪欲に選択していくのが最善である．したがって，$a \gt k$ での同値性を仮定し，$a = k$ で成立を示せばよい．
　$k$ が $(1)$ をみたすとき，$k$ とちょうど $2020$ 桁が一致する数は，$(1)$ の左辺において $k$ から一文字のみが変化するから，$(1)$ をみたさない．仮定よりそのような数は $X$ に含まれないから，$k\in X$ である．
　逆に $k$ が $(1)$ をみたさないとき，$(1)$ の左辺の値を二進法で表したときに，$1$ となる桁の中で最も位の大きなものをとれる．$b_i$ の中から同じ桁が $1$ となるものを一つ任意にとり，$(1)$ が成立するような $b^\prime_i$ に変更してできた数を $a^\prime$ とすれば，$b_i \gt b^\prime_i$ より $a \lt a^\prime$ で，さらに $a^\prime \in X$ であるから，$a \notin X$ が従う．
　したがって，以下 $(1)$ をみたす組 $(b_1, \ldots, b_{2021})$ を数え上げればよい. $b_1, \ldots , b_{2021}$ の中で $8$ の位が $0$ であるものが存在するから，その中で最も添字の大きいもので $1, 2, 4$ の位を調整することを考えれば，求める値は $$\begin{aligned} \lvert X \rvert &= \sum_{n=0}^{1010} \Bigl({}_{2021}\mathrm{C}_{2n} \times 8^{2021-2n-1}\times 2^{2n}\Bigr) \\ &= 2^{2017}\times2\sum_{n=0}^{1010} \Bigl({}_{2021}\mathrm{C}_{2n} \times 4^{2021-2n}\Bigr) \\ &= 2^{2017}((4+1)^{2021}+(4-1)^{2021}) = 2^{2017}(5^{2021} + 3^{2021}) \end{aligned}$$ Fermatの小定理などよりこれを $1009$ で割った余りは $\textbf{682}$ である．