BZOJ1815: [Shoi2006]color 有色图 群论+Polya定理+组合数学
题解：
具体请参考http://wyfcyx.is-programmer.com/posts/181716.html
对于这道题目则要注意一点复杂度的问题，否则会T。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #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;} |
评论 (0)