Independent Ranges

ヒント: 実はこの問題は $N\leq 10^9$ でも解くことができます。

かいせつ:
互いに異なる $4$ つの整数を選ぶ方法は $\frac{N\times(N-1)\times(N-2)\times(N-3)}{4!}$ 通りです。 $4$ つの整数の $x,y,z,w$ への割り当て方のうち、区間が共通部分を持たないのは何通りでしょうか。

これは $N=4$ のときの答えなので $2$ 通りです。

したがって、 $\frac{N\times(N-1)\times(N-2)\times(N-3)}{4!}\times2=\frac{N\times(N-1)\times(N-2)\times(N-3)}{12}$ が答えです。