[CF340E] Iahub and Permutations

给定两个大小相等的集合 $A,B$，求满足 $f(i)\not=i$ 的双射 $f$ 的数量。

若 $A=B$ 则为错排问题，所以我们考虑类似地通过递推解决这个问题。

令 $S=A\cap B$，设 $f(n,m)$ 为 $|S|=n,|A|=|B|=n+m$ 时这样的双射 $f$ 的数量。

显然 $f(0,m)=m!$。$n>0$ 时我们令 $t=\inf S$，对所有 $f$ 按照 $f(t)$ 进行分类讨论：

• 若 $f(t)\in S$ 且 $f(t)=f^{-1}(t)$，显然有这种情况下所有合法 $f$ 到 $A,B$ 均去掉 $t,f(t)$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n-1)f(n-2,m)$
• 否则，通过令 $f^{-1}(t)$ 映射到 $f(t)$，可以得到所有合法 $f$ 到 $A,B$ 均去掉 $t$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n+m)f(n-1,m)$。

由此可以得到递推式 $f(n,m)=(n-1)f(n-2,m)+(n+m)f(n-1,m)$。可见合法的状态只有 $O(n)$ 种。