P3750 [Six-Province Joint Exam 2017] Breakup Is a Blessing

> Zeit und Raum trennen dich und mich. Time and space separate you and me. B-kun is playing a game with $n$ lights and $n$ switches. The $n$ lights have initial states and are indexed by the positive integers from $1$ to $n$. Each light has two states, on and off. We use $1$ to indicate the light is on and $0$ to indicate it is off. The goal of the game is to turn all lights off. When operating the $i$-th switch, the states of all lights whose indices are divisors of $i$ (including $1$ and $i$) are toggled, i.e., on becomes off, and off becomes on. B-kun finds this game difficult, so he considers the following strategy: at each step, uniformly at random choose one switch to operate, until all lights are off. This strategy may require many operations, so B-kun thinks of the following optimization. If, in the current state, it is possible to turn all lights off by pressing at most $k$ switches, then he will stop acting randomly and directly choose a method with the minimum number of operations (which is clearly at most $k$) to press those switches. B-kun wants to know the expected number of operations under this strategy (that is, act randomly first, and finally, if at most $k$ steps suffice, use the method with the minimum number of operations). This expectation may be large, but B-kun observes that the expectation multiplied by $n!$ is always an integer, so he only needs this integer modulo $100003$.

The first line contains two integers $n, k$. The next line contains $n$ integers, each being $0$ or $1$, where the $i$-th integer indicates the initial state of the $i$-th light.

Output one line: the expectation of the number of operations multiplied by $n!$, modulo $100003$.

For $0\%$ of the testdata, the input is identical to the sample. For an additional $30\%$ of the testdata, $n \leq 10$. For an additional $20\%$ of the testdata, $n \leq 100$. For an additional $30\%$ of the testdata, $n \leq 1000$. For $100\%$ of the testdata, $1 \leq n \leq 100000, 0 \leq k \leq n$. For each of the above parts of the testdata, half of the testdata satisfies $k = n$. Translated by ChatGPT 5