Problem 539

Odd elimination

Start from an ordered list of all integers from $1$ to $n$. Going from left to right, remove the first number and every other number afterward until the end of the list. Repeat the procedure from right to left, removing the right most number and every other number from the numbers left. Continue removing every other numbers, alternating left to right and right to left, until a single number remains.

Starting with $n = 9$, we have:

$\underline{1}\ 2\ \underline{3}\ 4\ \underline{5}\ 6\ \underline{7}\ 8\ \underline{9}$

$2\ \underline{4}\ 6\ \underline{8}$

$\underline{2}\ 6$

$6$

Let $P(n)$ be the last number left starting with a list of length $n$.

Let $\displaystyle S(n) = \sum_{k=1}^n P(k)$.

You are given $P(1)=1$, $P(9) = 6$, $P(1000)=510$, $S(1000)=268271$.

Find $S(10^{18})\bmod{987654321}$.

奇数位消除

考虑由$1$至$n$之间全体整数组成的有序数列。先从左往右，消除所有从左数起奇数位上的数，再从右往左，消除所有从右数起奇数位上的数；不断重复这一过程，直到只剩下一个数。

例如，若一开始$n = 9$，则有：

$\underline{1}\ 2\ \underline{3}\ 4\ \underline{5}\ 6\ \underline{7}\ 8\ \underline{9}$

$2\ \underline{4}\ 6\ \underline{8}$

$\underline{2}\ 6$

$6$

记$P(n)$为初始数列长度为$n$时最后剩下的数。

令$\displaystyle S(n) = \sum_{k=1}^n P(k)$。

已知$P(1)=1$，$P(9) = 6$，$P(1000)=510$，$S(1000)=268271$。

求$S(10^{18}) \bmod{987654321}$。