算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
二维偏序
高维前缀和
树上差分
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
动态开点线段树
线段树的合并(一)
可持久化线段树
树链剖分
平衡树
FHQ-Treap
珂朵莉树
分块
位分块
字符串
数学
组合计数
二项式定理
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
流和匹配
最大流
最大流的一些应用
图论杂项
最大团搜索算法
树上问题
kruskal重构树
kruskal重构树的一些问题
动态规划
计算几何
杂项
启发式合并
高精度
一些经典问题
约瑟夫环
曼哈顿距离
多重集合的排列组合
排列与置换
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
杂项
启发式合并
高精度
一些经典问题
约瑟夫环
曼哈顿距离
多重集合的排列组合
排列与置换
[[ item.c ]]
0
0
排列与置换
## 排列的奇偶性 每一个排列$$p$$,都可以**环分解**,即分解成若干不相交的环 而对于每个环,$$(i, to_i)$$表示相邻的边,假设环的大小是$$|L|$$(有$$L$$条边) 那么变换成**单位排列,最少需要交换的次数**是$$(|L| - 1)$$ 所以总的交换次数是 ```math \displaystyle \sum_{c \in cycles} (|L| - 1) = n - cycles ``` 所以做一次环分解,求出有$$cycles$$个不相交的环,那么排列的奇偶性等于$$(n - cycles) \bmod 2$$ 同时,**排列的奇偶性 = 排列逆序对的个数** 因为每存在一对逆序对,就意味着还原成单位排列,需要一次交换
看完文章有啥想法
发布评论
目录
[[ item.c ]]
44 人参与,0 条评论