题解 P3795 【钟氏映射】

· · 题解

作为出题人我很方啊

到底算不算数学题呢？

我想应该算用到了组合吧

其实是动归啦。。。

设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