bzoj 1025 [SCOI2009]游戏（置换群，DP）
【题目链接】http://www.lydsy.com/JudgeOnline/problem.php?id=1025【题意】给定n，问1..n在不同的置换下变回原序列需要的不同排数有多少种。【思路】对于一个置换，如果分解后的到的循环长度为A1,A2,A3…则答案为lcm(A1,A2…)的不同种数，即...
POJ 3270 Cow Sorting(置换群)
题目链接很早之前就看过这题，思路题把，确实挺难想的，黑书248页有讲解。#include<cstdio>#include<cstring>#include<iostream>#include<cmath>#include<algorithm>...
【BZOJ】1025: [SCOI2009]游戏（置换群+dp+特殊的技巧+lcm）
http://www.lydsy.com/JudgeOnline/problem.php?id=1025首先根据置换群可得$$排数=lcm\{A_i,A_i表示循环节长度\},\sum_{i=1}^{k}A_i=n$$根据lcm的定义，分解质因数拆掉$A_i=p_1^{x_1}\timesp_2^{...
BZOJ 1025: [SCOI2009]游戏 [置换群 DP]
传送门题意：求$n$个数组成的排列变为升序有多少种不同的步数步数就是循环长度的$lcm$.....那么就是求$n$划分成一些数几种不同的$lcm$咯然后我太弱了这种$DP$都想不出来....通过枚举每个质因子的指数来求$lcm$$d[i][j]$表示前$i$个质因子当前和为$j$的方案数转移枚举质因...