【题目分析】
同样是Burnside引理。但是有几种颜色是不能放在一起的。
所以DP就好了。
然后T掉
所以矩阵乘法就好了。
然后T掉
所以取模取的少一些，矩阵乘法里的取模尤其要注意，就可以了。
A掉
【代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define maxn 11
#define ll long long
#define inf 0x3f3f3f3f
#define maxm 100005
const int md=9973; int T,n,m,k,ni,ispr[maxm],pr[maxm],top=0,sum; struct Matrix{
int x[maxn][maxn];
void init(){memset(x,0,sizeof x);}
void clear(){F(i,1,m)F(j,1,m)x[i][j]=1;}
void print()
{
F(i,1,m)
{
F(j,1,m) printf("%d ",x[i][j]);
printf("\n");
}
}
}A,B,C,D; Matrix operator * (const Matrix a,const Matrix b) {
Matrix c;
for (int i=1;i<maxn;++i)
for (int j=1;j<maxn;++j)
{
c.x[i][j]=0;
for (int k=1;k<maxn;++k)
c.x[i][j]+=a.x[i][k]*b.x[k][j];
c.x[i][j]%=md;
}
return c;
} void init()
{
F(i,2,maxm-1)
{
if (!ispr[i]) pr[++top]=i;
F(j,2,inf)
{
if (i*j>=maxm) break;
ispr[i*j]=1;
}
}
} int qpow(int a,int b)
{
int ret=1;a%=md;
while (b)
{
if (b&1) (ret*=a)%=md;
(a*=a)%=md;
b>>=1;
}
return ret;
} int phi(int n)
{
int ret=n;
for (int i=1;pr[i]*pr[i]<=n&&i<=top;++i)
if (n%pr[i]==0)
{
ret=ret-ret/pr[i];
while (n%pr[i]==0) n/=pr[i];
}
if (n>1) ret=ret-ret/n;
return ret%md;
} int tak(int b)
{
int ret=0;
D.init();F(i,1,m)D.x[i][i]=1;
C=B;
while (b)
{
if (b&1) D=D*C;
C=C*C;
b>>=1;
}
F(i,1,m) ret+=D.x[i][i];
return ret;
} int main()
{
init();
scanf("%d",&T);
while (T--)
{
sum=0;
scanf("%d%d%d",&n,&m,&k);
ni=qpow(n,md-2);
B.init();
B.clear();
F(i,1,k)
{
int a,b;
scanf("%d%d",&a,&b);
B.x[a][b]=B.x[b][a]=0;
}
for (int i=1;(ll)i*(ll)i<=(ll)n;++i)
{
if (n%i==0)
{
sum=(sum+tak(i)*phi(n/i))%md;
if (i*i!=n)
sum=(sum+tak(n/i)*phi(i))%md;
}
}
printf("%d\n",(sum*ni)%md);
}
}