自动搬运

查看原文

来自洛谷，原作者为

	XZYQvQ **

搬运于2025-08-24 21:52:47，当前版本为作者最后更新于2017-06-02 21:10:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为出题人我很方啊

到底算不算数学题呢？

我想应该算用到了组合吧

其实是动归啦。。。

设$g(i)$为集合N=M={1,2,3,....,i}的时候符合条件的映射个数

$g(0)=g(1)=1$

$g(i)=g(i-1)+g(i-2)*(i-1)$

答案为$g(k)$

解释：因为满足$f[f(x)]=x$，所以如果f(x)=y，那么f(y)=x（即形成一个x型的交叉映射）

对于g(i)：

N中的一个元素x，要不就是f(x)=x,要不就是f(x)=y

如果f(x)=x，那么就把x从N、M中拿走，两边元素个数变为i-1，所以方案数为$g(i-1)$

如果f(x)=y，那么就把x、y从N、M中拿走，两边元素个数变为i-2，有n-1个不同的y可以选择，所以方案数为$(n-1)*g(i-2)$

所以加起来就是$g(i-1)+g(i-2)*(i-1)$

由于空间只有20MB，要开滚动数组，记得取模，会爆int