AtCoder Beginner Contest 235 G 問題 Gardens

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$A$ 株のリンゴの苗, $B$ 株のバナナの苗, $C$ 株のサクランボの苗がある. これらの苗を $N$ 個の庭に植える. ただし, 以下の条件を満たさなければならない.

(a) 全ての庭には少なくとも1株以上の苗を植える.
(b) 1つの庭に同種の果物の苗がない.
(c) 全ての株を植える必要はない.

この条件を満たすような苗の植え方の数を求めよ.

制約

$1 \leq N \leq 5 \times 10^6$
$0 \leq A,B,C \leq N$

解法

包除原理の利用

包除原理を利用する.

包除原理

有限集合 $X$ における $N$ 個の集合 $A_1, \dots, A_N \subset X$ に対して,

$\displaystyle \left|\bigcap_{i=1}^N A_i \right|=\sum_{S \subset [\![N]\!]} (-1)^{|S|} \left|\bigcap_{j \in S} A_j^c \right|$

が成り立つ. ただし, $[\![N]\!] =\{1,2, \dots,N \}$ とする.

包除原理を利用するために, 集合 $X, A_1, \dots, A_N$ を考える. 以下のように設定するのが良い

集合 $X$ を条件 (b), (c) を満たすような果物の苗の植え方とする.
集合 $A_1, \dots, A_N$ を $i$ 番目の庭には1つ以上の果物の苗を植えているような植え方とする.

このとき, $\displaystyle \left|\bigcap_{j \in S} A_j^c \right|$ は $S=\{j_1, \dots, j_k\}$ として, $j_1, \dots, j_k$ 番目の庭には果物を植えていないような植え方の数になる. この場合の数は対称性から, $k$ のみによる.

よって, $|S|=k$ の場合における $\displaystyle \left|\bigcap_{j \in S} A_j^c \right|$ の値を $H_k$ とすると,

$\displaystyle \left|\bigcap_{i=1}^N A_i \right|=\sum_{k=0}^N (-1)^k \dbinom{N}{k} H_k$

になる.

なお, 以降では説明を簡単にするのため, $F_k:=H_{N-k}$ とする. つまり,

$\displaystyle \left|\bigcap_{i=1}^N A_i \right|=\sum_{k=0}^N (-1)^{N-k} \dbinom{N}{k} F_k$

を求める.

$F_k$ を求める.

$F_k$ は $k$ 個の庭に制限した問題において, (b), (c) を満たすような場合の数である. ここで, (b), (c) は各果物ごとに独立に考えることができる.

$D$ 株の苗を持っている果物について考える. $k$ 個の庭に重複なく高々 $D$ 株を植えることになる. このような苗の植え方 $T_k(D)$ は,

$\displaystyle T_k(D)=\sum_{r=0}^D \dbinom{k}{r}$

となる.

そして, $F_k=T_k(A) T_k(B) T_k(C)$ である.

ここで, 必要な値は $T_0(D), \dots, T_N(D)$ の $N+1$ 個の値であるが, これを愚直に計算しようとしても $O(N^2)$ で間に合わない. しかし, 二項係数における性質を利用することにより, 高速に求めることができるようになる.

二項係数の性質

今回の性質で利用する性質を述べる.

$n,r$ を非負整数とする. このとき,

$\dbinom{n+1}{r}=\dbinom{n}{r}+\dbinom{n}{r-1}$

が成り立つ.

(証明)

$r \leq n$ のとき

$\begin{align} \dbinom{n}{r}+\dbinom{n}{r-1} &=\dfrac{n!}{r!(n-r)!}+\dfrac{n!}{(r-1)!(n-r+1)!} \\ &=\dfrac{n!(r+(n-r+1))}{r!(n-r+1)!} \\ &=\dfrac{n!(n+1)}{r!(n-r+1)!} \\ &=\dfrac{(n+1)!}{r!(n-r+1)!} \\ &=\dbinom{n+1}{r} \end{align}$

である.

$r=n+1$ のとき

$\dbinom{n+1}{r}=\dbinom{n+1}{n+1}=1, \quad \dbinom{n}{r}+\dbinom{n}{r-1}=\dbinom{n}{n+1}+\dbinom{n}{n}=1$

である.

$r \gt n+1$ のとき

$\dbinom{n+1}{r}=0, \quad \dbinom{n}{r}+\dbinom{n}{r-1}=0$

である.

$T_k(D)$ を高速に求める.

上で示した性質から, 以下のようにして $T_0(D), \dots, T_N(D)$ を高速に求めることができる.

$\begin{cases} T_0(D)=1 \\ T_{k+1}(D)=2T_k(D)-\dbinom{k}{D} & (k \geq 1) \end{cases}$

証明

$k=0$ のとき,

$\displaystyle T_0(D)=\sum_{r=0}^D \dbinom{0}{r}=\dbinom{0}{0}+\dbinom{0}{1}+\dots+\dbinom{0}{D}=1+\underbrace{0+\dots+0}_{D}=1$

である.

$k$ のときに成り立っているとする. $k+1$ のとき

$\displaystyle \begin{align} T_{k+1}(D) &=\sum_{r=0}^D \dbinom{k+1}{r} \\ &=\sum_{r=0}^D \left(\dbinom{k}{r}+\dbinom{k}{r-1} \right) \\ &=\sum_{r=0}^D \dbinom{k}{r}+ \sum_{r=0}^D \dbinom{k}{r-1} \\ &=T_{k}(D)+\sum_{s=0}^{D-1} \dbinom{k}{s} \\ &=T_{k}(D)+\sum_{s=0}^D \dbinom{k}{s}-\dbinom{k}{D} \\ &=T_{k}(D)+T_k(D)-\dbinom{k}{D} \\ &=2T_{k}(D)-\dbinom{k}{D} \\ \end{align}$