题意：
用m种颜色涂n个小球组成的项链，其中k对颜色不能相邻，求一共有多少种方案。
分析：
polya计数，难点是对于一个置换p,怎样确定在p下等价的方案数。设p的循环节数为i,如果没有限制显然是m^i,有限制的话怎么办呢？考虑将每一种方案转化为路径，比如a->b->c->a,那么循环节数为i的方案数就是a到a加上b到b...长为i的不同路径数。.
代码：
//poj 2888
//sep9
#include <iostream>
using namespace std;
typedef __int64 INT;
const int mod=9973;
const int maxN=36000;
int n,m,k;
int mat[16][16],tmp[16][16],tp[16][16];
int prime[maxN+10],vis[maxN+10];int phi(int n)
{int res=n;for(int i=0;prime[i]*prime[i]<=n;++i){if(n%prime[i]==0){res=res/prime[i]*(prime[i]-1);while(n%prime[i]==0) n/=prime[i];} } if(n>1)res=res/n*(n-1);return res%mod;
}int pow(int a,int b)
{int ans=1;a=a%mod;while(b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}void init()
{memset(vis,0,sizeof(vis));int k=0;for(int i=2;i<maxN;++i){if(!vis[i])prime[k++]=i;for(int j=0;j<k&&i*prime[j]<maxN;++j){vis[i*prime[j]]=1;if(!i%prime[j]) break;} }
}
void mul(int a[16][16],int b[16][16])
{int c[16][16];for(int i=0;i<m;++i)for(int j=0;j<m;++j){c[i][j]=0;for(int k=0;k<m;++k)c[i][j]+=a[i][k]*b[k][j]; c[i][j]%=mod;}for(int i=0;i<m;++i)for(int j=0;j<m;++j)a[i][j]=c[i][j];
}int find(int x)
{memset(tmp,0,sizeof(tmp));for(int i=0;i<m;++i)tmp[i][i]=1;for(int i=0;i<m;++i)for(int j=0;j<m;++j)tp[i][j]=mat[i][j];while(x){if(x&1)mul(tmp,tp);mul(tp,tp);x>>=1;}int ans=0;for(int i=0;i<m;++i)ans=(ans+tmp[i][i])%mod;return ans;
}int main()
{init();int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;++i)for(int j=0;j<m;++j)mat[i][j]=1;while(k--){int a,b;scanf("%d%d",&a,&b);a--,b--;mat[a][b]=mat[b][a]=0;}int ans=0;for(int i=1;i*i<=n;++i){if(i*i==n){ans=(ans+find(i)*phi(i)%mod)%mod;}else if(n%i==0){ans=(ans+find(i)*phi(n/i)%mod)%mod;ans=(ans+find(n/i)*phi(i)%mod)%mod;}}printf("%d\n",(ans*pow(n,mod-2))%mod);}
}