If we know the answer when person \(0\) is always chosen, we can multiply it by \(L/N\) to get the original answer.

Let’s assume that person \(0\) is always chosen. For each \(D = 1, 2, \cdots\), it suffices to find the number of ways to choose people so that the cost is less than \(D\).

First, people \(D, \cdots, L - D\) cannot be chosen.

Next, consider whom to choose among people \(1, 2, \cdots, D - 1\). They can be chosen freely without interfering with each other.

Finally, consider whom to choose among people \(L - D + 1, \cdots, L - 1\). The condition for choosing person \(i\) is that none of the people in \([i - L + D, i - D]\) have been chosen so far. Here, this interval is basically included within \([1, D - 1]\). If \(2D \leq i\), this interval extends beyond that range, but the exceeding part is included in \([D, L - D]\), from which we already know we are not choosing anyone, so we don’t need to consider it specially.

Let \(W = L - 2D + 1\). We can regard the operation of choosing people from \(L - D + 1, \cdots, L - 1\) as the operation of choosing intervals of length \(W\) among people \(1, \cdots, D - 1\).

Then, what we need to consider is selecting people and intervals from people \(1, \cdots, D - 1\) so that they do not overlap (it’s acceptable for intervals themselves to overlap).

We will call a person chosen in the people selection as a red person. Also, in the interval selection, we will call the starting person of the interval as a blue person.

If we fix the number of times red and blue alternate, the total number of ways to choose can be expressed using binomial coefficients. Also, the number of alternations is at most \(N / W\).

Therefore, if we perform this calculation for all \(D\), the total computational complexity is \(O(N + N/2 + N/3 + \cdots) = O(N \log N)\), so it runs sufficiently fast.

Sample Solution (C++)