\(n\) 個のワインから条件を満たすように \(k\) 個の要素を取る方法の通り数を \(F(n,k)\) と表すことにします． また，\(1 \leq i \leq n\) に対して，\(i\) 番目の要素が選ばれる通り数を \(G(n,k,i)\) と表します． 目標は，\(G(N,K,i)\) をすべての \(i\) に対して求めることです．

\(D \leq i \leq N-D+1\) について考えます． \(G(N,K,i)\) は，\(N\) 個のワインから \(K-1\) 個を間隔 \(D\) 以上空けて選び，その際に左から \(i-D+1,\cdots,i+D-1\) 番目を選ばないようにする場合の数です． これは，\(N-D\) 個のワインから \(K-1\) 個を間隔 \(D\) 以上空けて選び，その際に左から \(i-D+1,\cdots,i-1\) 番目を選ばないようにする場合の数です． これは，\(F(N-D,K-1)-\sum_{i-D+1 \leq j \leq i-1} G(N-D,K-1,j)\) です．

\(i \leq D-1\) 及び \(N-D+2 \leq i\) についても，同様の式を作ることができます．ただし，\(\sum_j G(N-D,K-1,j)\) の \(j\) が動く範囲は少し異なります．

この関係式を用いて，次のようなアルゴリズムを考えることができます．

• \(V(t)=(G(N-tD,K-t,1),G(N-tD,K-t,2),\cdots,G(N-tD,K-t,N-tD))\) と定義し，\(V(t-1)\) を\(V(t)\) から上述の式を用いて求めることを繰り返し，\(V(0)\) を得る．

以降，便利のため，数列 \(V(t)\) を多項式の係数列とみなし，多項式の操作を行うことにします． \(V(t)\) から \(V(t-1)\) を求める際の操作は，大まかにいえば以下のとおりです．

1. \(V(t)\) に \(\sum_{1 \leq i \leq D-1} -x^i\) を乗算する．
2. \(V(t)\) の全ての項に一定の値(\(=F(N-tD,K-t)\))を足す．

まず，2. についてですが，これは，すべての項に \(foo\) という値が足されている，というデータを持つことで，実際には足し算を行う必要がなくなります． ただしその代わり，最低次の \(D-1\) 項と最高次の \(D-1\) 項では値がずれるので，このずれを打ちすように値を足すことにします．なお，ここで足されるべき値は，\(foo\) の値によって決定するため，簡単に計算できます．

ここで，最高次の \(D-1\) 項の修正を行わないで答えを求めることを考えます． このようにして得られた \(V(t)\) はもちろん間違った値を保持しています．しかし，対称性を考えると，低次の項の修正が \(1,2,\cdots\) 項目に与える影響と，高次の項が \(N,N-1,\cdots\) に与える影響は完全に等しいです． よって，低次の項による影響を求めさえすれば，それ反転すれば高次の項の影響も知ることができます．

結局，必要な操作は

• \(V(t)\) に \(\sum_{1 \leq i \leq D-1} -x^i\) をかけて，予め計算した \(D-2\) 次多項式を足す．

だけになります． これは分割統治+FFTを使い，\(O(N\log(N)\log(N/D))\) で計算できます．

よって，このアルゴリズムは全体で \(O(N\log(N)\log(N/D))\) 時間で動作します．