组合计数（polya计数）：SGU 282 Isomorphism

　　因为论文的题解写得太好了，直接贴。
 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 typedef long long LL;

 const int N=;int st[N];

 LL n,m,Mod,fac[N],ifac[N],pow[N],ans;

 LL Inv(LL x){return x==?x:(Mod-Mod/x)*Inv(Mod%x)%Mod;}

 LL Gcd(LL a,LL b){return b?Gcd(b,a%b):a;}

 void DFS(int d,int c,int l){

     if(c==){

         LL tot=;int t=;

         for(int i=;i<=d;i++)

             tot=tot*Inv(st[i])%Mod;

         for(int i=;i<=d;i++)

             if(st[i]!=st[i-]){

                 tot=tot*ifac[t]%Mod;

                 t=;

             }

             else t+=;

         tot=tot*ifac[t]%Mod;

         for(int i=;i<=d;i++)

             tot=tot*pow[st[i]/]%Mod;

         for(int i=;i<=d;i++)

             for(int j=i+;j<=d;j++)

                 tot=tot*pow[Gcd(st[i],st[j])]%Mod;

         ans=(ans+tot)%Mod;

     }

     for(int i=l;i<=c;i++)

         st[d+]=i,DFS(d+,c-i,i);

 }

 int main(){

     scanf("%I64d%I64d%I64d",&n,&m,&Mod);

     pow[]=fac[]=ifac[]=;

     for(int i=;i<=n;i++){

         fac[i]=1ll*fac[i-]*i%Mod;

         pow[i]=pow[i-]*m%Mod;

         ifac[i]=Inv(fac[i]);

     }

     DFS(,n,);printf("%I64d\n",ans);

     return ;

 }