問題：E - NEQ
解答：Submission #14790587 - AtCoder Beginner Contest 172
解法：A、Bの数列の条件を言い換えると、①「同じ位置にあるAとBの要素は異なる」、②「数列Aの各要素は互いに異なる。また、数列Bの各要素も互いに異なる。」となる。
問題の設定としては攪乱順列に近い。攪乱順列は要素の種類数がn、選ぶ要素の個数もnであるが、この問題は要素の種類数がm、選ぶ要素の個数がnとなっている。また、攪乱順列はAの順列が与えられて、Bの順列の通り数を数えるが、この問題はAの順列もBの順列もそれぞれ通り数にカウントする。ただ、数列の数え方としては攪乱順列の考え方をそのまま使用できる。包除原理を用いて数えてゆく。
包除原理によって次のような言い換えが可能となる。
「数列Aと数列Bで要素が一致する位置がない数列の通り数」
=「数列Aと数列Bの全ての通り数」－「数列Aと数列Bで要素が一致する位置がある数列の通り数」
「数列Aと数列Bの全ての通り数」はmPn * mPnである。残りを数えてゆく。
Si := 数列Aと数列Bとでi番目が一致する（他は問わない）数列の集合 とする。
「数列Aと数列Bで要素が一致する位置がある数列の通り数」
= | S1 ∪ S2 ∪ ... ∪ Sn |
= Σ |Si| - Σ|Si ∩ Sj| + Σ|Si ∩ Sj ∩ Sk| + ... + (-1)n-1 * |S1 ∩ S2 ∩ ... ∩ Sn|
となる。
ここでΣ|Si1 ∩ Si2∩ ... ∩ Sit| は数列A、Bで一致する位置がit個以上ある数列の集合の通り数となる。
it = xとし、Σ|Si1 ∩ Si2∩ ... ∩ Sx| を次のように数える。
①Aを決める。通り数はmPn
②AとBが一致する位置を決める。通り数はmCx
③AとBが一致する位置のBの数字を決める。通り数は1
④AとBが一致しない部分のBの数字を決める。通り数はm-xPn-x
よって、Σ|Si1 ∩ Si2∩ ... ∩ Sx| = mPn * mCx * m-xPn-x である。
