【POJ2888】Magic Bracelet

题意：一个长度为n的项链，有m种颜色的珠子，有k个限制(a,b)表示颜色为a的珠子和颜色为b的珠子不能相邻，求用m种珠子能串成的项链有多少种。如果一个项链在旋转后与另一个项链相同，则认为这两串珠子是相同的。

$n\le 10^9,m\le 10,k\le \frac{m(m-1)} 2 $

题解：好题。

依旧回顾从Burnside引理到Pólya定理的推导过程。一个置换中的不动点要满足它的所有循环中的点颜色都相同，那么在旋转i次的置换中，循环有gcd(i,n)个，我们规定这些循环的起始点是1,2,...gcd(i,n)，由于1,1+i,1+2i...的颜色都与i是一样的，那么我们其实只需要考虑1到gcd(i,n)这段的染色方案数即可。如何统计呢？矩阵乘法！

但是枚举i仍然是行不通的，但我们可以考虑枚举d=gcd(i,n)，有多少个i满足gcd(i,n)=d呢？显然是$\varphi({n\over d})$！所以DFS所有n的约数即可。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int P=9973;int n,m,K,mx,tot,ans;struct M{	int v[12][12];	int * operator [] (const int &a) {return v[a];}	M () {memset(v,0,sizeof(v));}	M operator * (const M &a) const	{		M b;		int i,j,k;		for(i=1;i<=m;i++)	for(j=1;j<=m;j++)	for(k=1;k<=m;k++)	b.v[i][j]=(b.v[i][j]+v[i][k]*a.v[k][j])%P;		return b;	}}S,T[33];int cnt[20],p[20];inline int pm(int x,int y){	int z=1;	x%=P;	while(y)	{		if(y&1)	z=z*x%P;		x=x*x%P,y>>=1;	}	return z;}inline void PM(int y){	for(int i=mx;i>=0;i--)	if(y>=(1<
        
         tot)	{		memset(S.v,0,sizeof(S.v));		int i,j;		for(i=1;i<=m;i++)	S[i][i]=1;		PM(d-1);		for(i=1;i<=m;i++)	for(j=1;j<=m;j++)	if(T[0][i][j])	ans=(ans+phi%P*S[i][j])%P;		return ;	}	int i;	dfs(x+1,d,phi);	for(i=1;i
         
          1)	p[++tot]=t,cnt[tot]=1,phi*=t-1;	dfs(1,1,phi);	printf("%d\n",ans*pm(n,P-2)%P);}int main(){	int cas;	scanf("%d",&cas);	while(cas--)	work();	return 0;}//4 3 2 0 3 2 1 1 2 3 2 2 1 1 1 2 3 2 3 1 1 1 2 2 2