I think we should:

1) merge each connected components to one vertex and memorize number of vertices within it

2) compute expected distance between 0 and random vertex from its component (<=> sum of distances from 1)

3) the same for 1

4) expected distance between two randomly chosen vertices in other components (<=> sum of distances between each pair)

5) compute expected edge cost between each two components (<=> sum of edges between all pairs in fixed two components

6) do a dp on a graph which vertices are components, vertices and edges costs are those expected thingies I explained, where dp[mask] denotes expected distance from 0 to random original node from those components contained in a mask and prob[mask] denotes probability that we will obtain that mask durin our process

You first select wether you would invert first row in said table. Then for each column you count sum of associated values and sum of values but smallest one. Depending on oddity of number of zeroes you add one of this values to the answer (and add the other one for inverted first row)

If you flip two consecutive K-element subsequences (that is, (i, i + 1, ..., i + K - 1) and (i + 1, ..., i + K)), only two lamps get toggled (i and i + K).

Now it's crucial to note that every combination that is possible to do with K-element flips, can also be done with the following two:

• toggle first K lamps,
• toggle any two lamps distant by K.

(each toggling of K consecutive lamps is a compound of these operations). It's much simpler now. Of course, each operation can be done zero times or once (it's no use doing it more than once).

Let's say we haven't used first operation in optimal solution. Then our sequence dissolves into K sequences of elements distant by K, in which you can toggle two consecutive elements. This is easy to solve; if i-th sequence has an even number of turned off lamps, you can turn them all on; in opposite case it's obvious we can't turn them all on, but it's possible to leave off only the least valuable lamp in the sequence.

What if we use the first operation? Then we just toggle first K lamps and then do exactly the same steps as before.

// oops, I'm not the first :)

That wasn't clear for me why those moves mnbvmar explained are sufficient to obtain all possible configurations, but I proved that using linear algebra. In fact what we can achieve is a affine plane in Z₂ⁿ which can be reached from starting point using (linearly independent) n - k + 1 vectors consisting of k consecutive ones, so that affine plane has dimension n - k + 1 and number of possible flips of lights distant by k is n - k, so after adding switching first k lamps we will obtain n - k + 1 linearly independent vectors spanning the same affine plane :).

EDIT: Thinking about this one again... That is rather clear that those moves are sufficient. But that can also be a way to think about this :D.

Well, you can split lamps into subarrays with fixed remainder mod K. Then, since 2 operations applied on [i, i + K) and [i + 1, i + K + 1) only flip lamps i and i + K (neighbours in one subarray), you can achieve any state of a subarray that has the same xor of all bits as the initial one. That means if there was an even number of off lamps in a subarray, you can set them all on, and if it was odd, you need to set the weakest one off.

This is sufficient if the number of steps is even; if it's odd, you can flip some K consecutive lamps (it doesn't matter which) and repeat.