置换相关

通常与计数挂钩,在一个环中确定一个元素就可以确定一整个环

例题1: Function HDU - 6038

给出两个排列,问可行映射f(i)=b(f(a(i)))的数目

首先把公式中的i和ai都带入数字,看成通过b在映射函数值,

显然这是一些置换环,环中确定其中一个f(x)值就可以根据b函数推出整个环的值

接下来就要考虑,处理当前环,随便拿个元素出来,比方说f3,f5,f6之间构成三元环,通过b函数来映射

我现在就想知道f3能取b中的什么值,能通过b的映射让环成立

注意到b中元素是有固有映射关系的,这时候就要选b中的映射环,这个映射环的环长必须是a环的因子,

才能让整个a环依次通过b映射正确映射

link


原文地址:https://www.cnblogs.com/Drenight/p/8611786.html