Let \(F(n,k)\) be the number of ways to choose \(k\) bottles from \(n\) bottles. Also, for \(G(n,k,i)\), let \(G(n,k,i)\) be the number of ways among the above where the \(i\)-th bottle is chosen. Our objective is to find \(G(N,K,i)\) for every \(i\).

Consider \(D \leq i \leq N-D+1\). \(G(N,K,i)\) is the number of ways to choose \(K-1\) bottles from \(N\) bottles, with intervals of at least \(D\), while not choosing the \((i-D+1)\)-th, \(\cdots\), \((i+D-1)\)-th bottles. This is equal to the number of ways to choose \(K-1\) bottles from \(N-D\) bottles, with intervals of at least \(D\), while not choosing the \((i-D+1)\)-th, \(\cdots\), \((i-1)\)-th bottles, which is \(F(N-D,K-1)-\sum_{i-D+1 \leq j \leq i-1} G(N-D,K-1,j)\).

We can also build a similar formula for \(i \leq D-1\) and \(N-D+2 \leq i\), but with slightly different ranges for \(j\) in \(\sum_j G(N-D,K-1,j)\).

Using these relations, we can construct the following algorithm:

• Define \(V(t)=(G(N-tD,K-t,1),G(N-tD,K-t,2),\cdots,G(N-tD,K-t,N-tD))\) and obtain \(V(0)\) by repeatedly finding \(V(t-1)\) from \(V(t)\) using the above formulae.

Below, for convenience, we will see the sequence \(V(t)\) as the coefficient sequence of a polynomial and do operations for polynomials on it. Roughly speaking, we find \(V(t-1)\) from \(V(t)\) as follows:

1. Multiply \(V(t)\) by \(\sum_{1 \leq i \leq D-1} -x^i\).
2. Add to every term of \(V(t)\) a constant value (\(=F(N-tD,K-t)\)).

First, regarding 2., by maintaining data in the form “every term is added the value \(foo\),” we do not have to perform real additions. However, it will cause a misalignment of values between the lowest \(D-1\) terms and highest \(D-1\) terms, so we will add a value negating it. This value to add is determined by the value \(foo\) and can be easily computed.

Here, consider finding the answer without modifying the highest \(D-1\) terms. Doing so will cause \(V(t)\) to hold incorrect values, of course. However, by symmetry, the effect of the modification of lower terms to the \(1\)-st, \(2\)-nd, \(\cdots\), terms and that of the modification of higher terms to the \(N\)-th, \((N-1)\)-th, \(\cdots\), terms are identical. Thus, if we just find the effect of the modification of lower terms, we can also know that of the modification of higher terms by reversing it.

In the end, we only need to:

• multiply \(V(t)\) by \(\sum_{1 \leq i \leq D-1} -x^i\) and add to it a pre-computed polynomial with degree \(D-2\).’

We can do it with a divide-and-conquer algorithm with FFT in \(O(N\log(N)\log(N/D))\).

Thus, our algorithm runs in a total of \(O(N\log(N)\log(N/D))\) time.