ABC172 E - NEQ - かんプリンの学習記録

問題概要

${1}$ 以上 ${M}$ 以下の要素からなる長さ ${N}$ の数列 ${A,B}$ のうち, 以下の条件を満たすものの数を求めよ.

制約がそこそこ大きいのでDPとかじゃなさそう.

${\downarrow}$

制約が不一致条件のみなので, ${A}$ を決めた時に条件を満たす ${B}$ の数は同じ.

これを求めることができたら, 答えはそれの ${{}_{M}\rm{P}_{\textit{N}}}$ 倍となる.

${\downarrow}$

${A=[1,2,3,\cdots,N]}$ と固定する. ${B_i\neq i}$ となる数列 ${B}$ の数を求めたい. ${M=N}$ のとき, これは完全順列(攪乱順列)というものである.完全順列の数の求め方は典型で, 包除原理を用いるものが知られている.

これと同じように考えてみると数列 ${B}$ の数は,

$\sum_{k=0}^{N}{}_{M-k}{\rm{P}}_{N-k}×{}_{N}{\rm{C}}_{k}×(-1)^k$

これに ${{}_{M}\rm{P}_{\textit{N}}}$ をかけてやれば答えになる. 階乗や階乗の逆元を前計算しておくと高速に計算できる.

完全順列を知っていたらすぐ解法は思いつきそう. 知らなくても包除原理っぽいので頑張ればできる.