polya定理板子题...
其实本题难度并不大，但是对我这种初学群论的蒟蒻还是很大一个挑战
首先看见这种带同构的计数，我们应该先把polya扔进来
$ans=frac{1}{|G|}sum_{i=1}^{|G|}m^{c(p_{i})}$
然后我们挨个去找就好了
$G$显然是一个对应边置换的置换群
m是已知，不用管，$|G|=n!$（一个点置换唯一对应一个边置换，因此边置换群的大小与点置换群的大小相等）
因此有一个最暴力的思想，就是每次$O(n!)$枚举所有置换进行计算，这样做...显然过不去这道题
因此我们换一种思想：
我们发现，本题真正的难点是：我们每次置换的方式是对点进行置换，而在计算时需要用的是边的置换！
因此首先我们要找到一个点的置换与边的置换的对应关系
怎么对应？
我们设一个点置换为$(a_{1},a_{2},...a_{n})(b_{1},b_{2}...b_{m})...$
则边可以被分为两类：
一.边的两个端点在同一个循环中
设一个循环中点的个数为$v_{i}$，那么这个循环中对应的边的个数显然是$C_{v_{i}}^{2}$，而为了研究这些边所在的等价类数，我们将这些点均匀分布在一个圆周上，那么在循环的作用下每条边都会沿圆周移动，那么移动的两条边不能重合当且仅当两条边长度不同（这里的边长都指圆上劣弧长），那么这个边集中一共有$frac{v_{i}}{2}$个等价类
二.边的两个端点不在同一个循环中
设两个循环中点的个数分别为$v_{i}$,$v_{j}$,那么这两个点集相互间能组成的边的个数为$v_{i}v_{j}$，对于一条边，在经过$LCM(v_{i},v_{j})$次置换后会回到本身，因此总的循环个数应该为$gcd(v_{i},v_{j})$
因此，对于一组给出的点的置换，设这组置换的循环节数量为$k$，那么这组点置换对应的边置换的循环节个数为$sum_{i=1}^{k}frac{v_{i}}{2}+sum_{i=1}^{k}sum_{j=i+1}^{k}gcd(i,j)$
那么这一组边置换对应的贡献也就是$m^{sum_{i=1}^{k}frac{v_{i}}{2}+sum_{i=1}^{k}sum_{j=i+1}^{k}gcd(i,j)}$
可是如果我们这么找，仍然会有$n!$个置换来计算，这样做还是会T
但是我们不难发现，边置换的贡献只与其结构有关，而结构相同的点置换一定会导出结构相同的边置换！
因此我们只需枚举所有点置换的结构即可
再考虑：对于每一个点置换，都满足一个表达式：$sum_{i=1}^{k}v_{i}=n$
那么一个点置换的结构不就是n的一个拆分嘛
考虑n很小，所以我们可以爆搜一发n的拆分
但是...具有这种结构的点置换一共会有多少个呢?
令$B_{i}$表示这种结构下大小相同的循环的个数，则结论某一种结构的点置换个数是$S=frac{n!}{prod_{i=1}^{k}v_{i}*prod_{i=1}^{k}B_{i}!}$
于是答案也就来了：
$ans=frac{1}{n!}sum S*m^{sum_{i=1}^{k}frac{v_{i}}{2}+sum_{i=1}^{k}sum_{j=i+1}^{k}gcd(i,j)}$
贴代码：
#include <cstdio> #define ll long long using namespace std; ll n,m,p; ll mul[65]; ll num[65]; ll GCD[65][65]; ll ret=0; ll pow_mul(ll x,ll y) { ll ans=1; while(y) { if(y&1)ans=ans*x%p; x=x*x%p,y>>=1; } return ans; } ll gcd(ll x,ll y) { return y?gcd(y,x%y):x; } void init() { mul[0]=mul[1]=1; for(ll i=2;i<=n;i++)mul[i]=mul[i-1]*i%p; for(ll i=1;i<=n;i++)for(ll j=i;j<=n;j++)GCD[i][j]=GCD[j][i]=gcd(i,j); } ll get_ans(int ttop) { ll sum=0,fm=1,cnt=0; for(int i=1;i<=ttop;i++) { sum=sum+(num[i]>>1),fm=(fm*num[i]%p); if(num[i]!=num[i-1])fm=fm*mul[cnt]%p,cnt=1; else cnt++; for(int j=i+1;j<=ttop;j++)sum=sum+GCD[num[i]][num[j]]; } fm=fm*mul[cnt]%p; ll S=pow_mul(fm,p-2); return S*pow_mul(m,sum)%p; } void dfs(int dep,ll ed,ll las) { if(!ed)ret=(ret+get_ans(dep-1))%p; else { for(ll i=las;i<=(ed>>1);i++) { num[dep]=i; dfs(dep+1,ed-i,i); num[dep]=0; } num[dep]=ed; dfs(dep+1,0,ed); num[dep]=0; } } int main() { scanf("%lld%lld%lld",&n,&m,&p); init(); dfs(1,n,1); printf("%lld ",ret); return 0; }