No.122

$\min(a, c, e, g) > \max(b, d, f)$ とする.

$\min(a, c, e, g) = k$ となる組み合わせの数を $A(k)$ とする. $a, c, e, g$ の中の $i$ が最小となる組み合わせの数を $B_i(k)$ とすると,

$$A(k) = \sum_{i \in \{a,c,e,g\}} B_i(k)$$

となる.

ここで $B_a(k)$ を考えると, $k < a_{min}$ または $k > a_{max}$ のときは $B_a(k) = 0$ である.

そうでない場合は $B_a(k)$ は, $c, e, g$ の範囲をそれぞれ $\max(i_{min}, k+1) \dots i_{max} \ i \in \{c, e, g\}$ としてこの $c, e, g$ の組み合わせの数となる. (どれかひとつでも範囲の最小が最大を上回った場合は $B_a(k) = 0$ である)

この組み合わせの数を求めるために包除の定理を使う.

$c, e, g$ それぞれの範囲の数の積を取り, ここから $c = e, e = g, g = c$ となる組み合わせの数を引く. $c = e$ となる組み合わせの数は $c, e$ の範囲の共通部分の範囲の数と $g$ の範囲の数の積である.

このままだと $c = e = g$ となる組み合わせの数を2回多く引いてしまっているので, 最後に $c = e = g$ となる組み合わせの数の2倍を足す.

$\max(b, d, f) = k$ となる組み合わせの数を $C(k)$ として, これも同様に計算する.

このとき, 求める組み合わせの数は,

$$\sum_k \left(A(k) \sum_{m=1}^{k-1} C(m) \right)$$

となる. $\sum C(k)$ は累積和を計算しておけば高速に計算できる.

$\max(a, c, e, g) < \min(b, d, f)$ の場合も同様に計算する.