ABC172 E - NEQ [解説]
いかつい見た目をしているが意外と簡単。
考えること
割とぱっと見で逃げ出したくなるような問題だが、まず $A$ を固定することを考える。そのためには $A$ の総数を考えたい。
単純な話だが、これは $1, 2, \ldots, M $ 以下の正整数から $N$ 個とるだけなので、$A$ の総数は $_MP_N$ と等しくなる。
あとは $A_i \neq B_i$ を満たすように $B$ を列挙するが、これが $Ο(N)$ でないと間に合わず、それにシンプルに列挙することもかなわない。$(M - 1)^N$ にしても全く見当違いな値になってしまう。
そこで、条件を満たす数列の個数を
$S = N$ 項であり、全ての要素が $M $ 以下で互いに相異なるような数列の集合
と定義したうえで、そのうえで包除原理を用いて求めることを考える。こうすると、
- $i$ 項以上が数列 $A$ と一致しているような数列 $B$ の総数
を $1$ 以上の全ての $i$ について求めることで、最終的に解を得られる。
$S$ は明らかにこれまた $_MP_N$ 種類の数列を含んでいる。
また、$i$ 項以上が数列 $A$ と一致しているような数列 $B$ の総数、といったが、これを求めるのは簡単で
$_NC_i \times (M-i)^{N-i}$
とするだけである。
一見、直感に反するかもしれないが、$i$ 項以上という条件が大事であり、ゆえに、必ず一致する $i$ 項を除いて、あと $N-i$ 項は重複していようがいなかろうがどうでもいいのだ。よってこの式は正当である。
なお、ちょうど $i$ 項が数列 $A$ と一致しているような数列 $B$ の総数、としてしまうのは誤りである(この場合、包除原理を使う前の条件と同じ理論で、どうしようもなくなる)。
あとは、全ての数列 $A$ について求めた $B$ の個数を掛けて、それが解である。
なお、脳が働いておらず $_nP_r$ を求めるために $_nC_r \times r!$ をしている。
