\(N\)が大きいため \((a,b,c,d)\) のすべての組を試すことはできません。まずは簡単なバージョンとして次の問題を考えてみます。

• 整数 \(N\),\(K\)が与えられます。2つの整数の組 \((a,b)\)であって、\(1 \leq a,b \leq N\) かつ \(a+b = K\) を満たすものの個数 \(f(N,K)\) を求めてください。

これは簡単な式で求まります。実際、 \(K=2,3,\ldots,2N\) に対して、\(f(N,K)=\min(K-1,2N+1-K)\) です。例えば、サイコロの2つの目の和の分布は\(K=2,..,12\) に対して順に\(1,2,3,4,5,6,5,4,3,2,1\) となっています。

もとの問題に戻ると、条件は \((a+b) - (c+d) = K\) と書けるので、まず \(x = a+b\) を固定します。すると条件は、\(a+b = x\) かつ \(c+d = x-K\) と書けるので、このときの答えへの寄与は \(f(N,x) \times f(N,x-K)\) となります。したがって \(x = 2,..,2N\) に対して上の値を足せば答えが求まります。

計算量は \(O(N)\) です。

なお、包除原理などを用いて \(O(1)\) で解くことも可能です。