BZOJ1815: [Shoi2006]color 有色图 群论+Polya定理+组合数学
题解:
具体请参考http://wyfcyx.is-programmer.com/posts/181716.html
对于这道题目则要注意一点复杂度的问题,否则会T。
代码:
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int n,m,p; int fac[61],ifac[61],_inv[61],g[61][61],powm[10010]; inline int gcd(int a,int b){ return(!b)?a:gcd(b,a%b); } inline int pow(int x,int y,int p){ int re=1,t=x; for(;y;y>>=1,t=(ll)t*t%p) if(y&1) re=(ll)re*t%p; return re; } inline int inv(int x){ return pow(x,p-2,p); } int stack[61],ans; inline void dfs(int last,int dep,int pre){ if(last==0){ int i,j,k,num=fac[n]; for(i=1;i<=dep;i=j+1){ for(j=i;j!=dep&&stack[j]==stack[j+1];++j); for(k=i;k<=j;++k) num=(ll)num*_inv[stack[i]]%p; num=(ll)num*ifac[j-i+1]%p; } int cir=0; for(i=1;i<=dep;++i) cir+=stack[i]>>1; for(i=1;i<=dep;++i) for(j=i+1;j<=dep;++j) cir+=g[stack[i]][stack[j]]; ans=((ll)ans+(ll)num*powm[cir])%p; return; } for(int i=pre;i<=last;++i){ stack[dep+1]=i; dfs(last-i,dep+1,i); } } int main(){ cin>>n>>m>>p; int i,j; for(fac[0]=1,i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%p; for(i=0;i<=n;++i) ifac[i]=inv(fac[i]); for(_inv[1]=1,i=2;i<=n;++i) _inv[i]=p-(ll)(p/i)*_inv[p%i]%p; for(i=1;i<=n;++i) for(j=1;j<=n;++j) g[i][j]=gcd(i,j); for(powm[0]=1,i=1;i<=10000;++i) powm[i]=(ll)powm[i-1]*m%p; dfs(n,0,1); cout<<(ll)ans*ifac[n]%p<<endl; return 0; }