\(2\) 変数の場合

整数 \((x,y)\) の組であって、 \(0\le x,y\le K\) かつ \(x+y=T\) なるものの個数を求める問題です。

\(T<0\) または \(T>2K\) のとき、答は存在しません。 \(T>K\) の場合、 \(x+y=T\iff (K-x)+(K-y)=2K-T\) より、 \(T\le K\) の問題に帰着できるので、それを仮定します。すると、 \(x+y=T\) より \((x,y)\) は \((0,T),(1,T-1),...,(T,0)\) しかありえませんが、 \(T\le K\) よりこれらは全て条件を満たすので \(T+1\) 通りです。

これより一般の \(T\) の場合、答は \(\max(0,\min(T+1,2K-T+1))\) 通りです。

なぜこのようになるかの証明は省略しますが、実際に \(T\) の範囲ごとのこの式の挙動を見てみると、今までの議論と整合性がとれることがわかります。

\(3\) 変数の場合

\(z\) を動かして考えると、答えは \(\sum_{z=0}^K\max(0,\min(S-z+1,2K-S+z+1))\) です。 \(0,S-z+1,2K-S+z+1\) の大小関係を定めると、 \(z\) の取りうる値が区間になります。また、その区間内での和は等差数列の和の公式により求められます。

これより時間計算量 \(O(1)\) で求めることができました。