首页 > 代码库 > BZOJ 1815: [Shoi2006]color 有色图 [Polya DFS 重复合并]
BZOJ 1815: [Shoi2006]color 有色图 [Polya DFS 重复合并]
传送门
题意：
染色图是无向完全图，且每条边可被染成k种颜色中的一种。
两个染色图是同构的，当且仅当可以改变一个图的顶点的编号，使得两个染色图完全相同。
问N个顶点，k种颜色，本质不同的染色图个数（模质数N≤53，P<109）。
想了一节课和一中午又看了课件
相同类型的循环合并的想法很巧妙
首先，点的置换对应唯一边的置换，我们可以枚举所有点的置换，找出每个置换下边置换的循环有多少个，然后套$Polya$公式
但是复杂度带叹号
我们发现，很多点置换类型是一样的，我们可以对$n$搜索划分来枚举点置换的类型(即每个循环的长度)，然后找出这种类型的置换有多少个
设每个循环长度$L_1,L_2,...,L_n$，那么相同类型的置换就相当于每个循环做圆排列，然后消除循环长度相同的影响
$\frac{n!}{L_1 L_2...L_n s_1! s_2!...s_t!}$
$s$为相同的长度的个数
那么如何从点的置换得到边的置换？
同一个循环里的边，他们的置换个数为$\frac{L}{2}$，具体可以把点排成一个圈画图观察一下
两个循环之间的边，他们的置换长度为$LCM(L_1,L_2)$，共有$L_1*L_2$条边，则个数为$GCD(L_1,L_2)$
然后就可以做了
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=60;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m,P;ll inv[N],fac[N],facInv[N];void ini(){ inv[1]=1;fac[0]=facInv[0]=1; for(int i=1;i<=n;i++){ if(i!=1) inv[i]=-P/i*inv[P%i]%P; if(inv[i]<0) inv[i]+=P; fac[i]=fac[i-1]*i%P; facInv[i]=facInv[i-1]*inv[i]%P; }}int L[N],tot;ll sum,ans;inline int gcd(int a,int b){return b==0 ? a : gcd(b,a%b);}inline ll Pow(ll a,int b){ ll re=1; for(;b;b>>=1,a=a*a%P) if(b&1) re=re*a%P; return re;}inline void mod(ll &x){if(x>=P) x-=P;}void dfs(int d,int now){ if(d==n){ int lo=0; ll cnt=fac[n],same=1; sort(L+1,L+1+tot); //printf("tot %d\n",tot); //for(int i=1;i<=tot;i++) printf("%d ",L[i]);puts("\n end"); for(int i=1;i<=tot;i++){ lo+=L[i]/2; for(int j=i+1;j<=tot;j++) lo+=gcd(L[i],L[j]); cnt=cnt*inv[L[i]]%P; if(i!=1&&L[i]==L[i-1]) same++; else if(same!=1) cnt=cnt*facInv[same]%P,same=1; } if(same!=1) cnt=cnt*facInv[same]%P; //printf("hi %d %lld\n",lo,cnt); mod(sum+=cnt); mod(ans+=cnt%P*Pow(m,lo)%P); //puts("\n"); }else{ for(int j=now;d+j<=n;j++){ L[++tot]=j; dfs(d+j,j); tot--; } }}int main(){ freopen("in","r",stdin); n=read();m=read();P=read(); ini(); dfs(0,1); //printf("%lld %lld\n",ans,sum); ans=ans*Pow(sum,P-2)%P; printf("%lld",ans);}
BZOJ 1815: [Shoi2006]color 有色图 [Polya DFS 重复合并]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。