这题虽然很老了但是挺好的
仍然套Burnside引理(因为有限制你并不能套Polya定理)，思路和这个题一样，问题主要是如何求方案。
思路是把放珠子的方案看成一张图，然后就巧妙的变成了一个经典的路径计数问题，这里可以多矩乘一次然后统计对角线，即强行让它走回一开始的珠子，比较方便
注：这代码T了，我不想卡了，但是复杂度和正确性没问题，请根据自己的情况食用
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int mod=9973; 6 int T,n,m,k,t1,t2,mapp[11][11]; 7 struct a 8 { 9 int mat[11][11]; 10 void Clean() 11 { 12 memset(mat,0,sizeof mat); 13 } 14 void Init() 15 { 16 for(int i=1;i<=m;i++) 17 for(int j=1;j<=m;j++) 18 mat[i][j]=mapp[i][j]; 19 } 20 }; 21 a Matime(a x,a y) 22 { 23 a ret; ret.Clean(); 24 for(int i=1;i<=m;i++) 25 for(int k=1;k<=m;k++) 26 for(int j=1;j<=m;j++) 27 ret.mat[i][j]+=x.mat[i][k]*y.mat[k][j]%mod,ret.mat[i][j]%=mod; 28 return ret; 29 } 30 a Maqpow(a x,int k) 31 { 32 if(k==1) return x; 33 a tmp=Maqpow(x,k/2); 34 return k%2?Matime(x,Matime(tmp,tmp)):Matime(tmp,tmp); 35 } 36 int Calc(int x) 37 { 38 a cal; int ret=0; 39 cal.Init(),cal=Maqpow(cal,x); 40 for(int i=1;i<=m;i++) 41 ret+=cal.mat[i][i],ret%=mod; 42 return ret; 43 } 44 int Phi(int x) 45 { 46 int ret=x; 47 for(int i=2;i*i<=x;i++) 48 if(x%i==0) 49 { 50 ret/=i,ret*=i-1; 51 while(x%i==0) x/=i; 52 } 53 if(x!=1) ret/=x,ret*=x-1; 54 return ret; 55 } 56 void exGCD(int a,int b,int &x,int &y) 57 { 58 if(!b) x=1,y=0; 59 else exGCD(b,a%b,y,x),y-=a/b*x; 60 } 61 int Inv(int x) 62 { 63 int xx,yy; 64 exGCD(x,mod,xx,yy); 65 return (xx%mod+mod)%mod; 66 } 67 int Solve(int x) 68 { 69 int ret=0; 70 for(int i=1;i*i<=x;i++) 71 if(x%i==0) 72 { 73 ret+=Phi(x/i)*Calc(i)%mod,ret%=mod; 74 if(i*i!=x) ret+=Phi(i)*Calc(x/i)%mod,ret%=mod; 75 } 76 return ret*Inv(x)%mod; 77 } 78 int main() 79 { 80 scanf("%d",&T); 81 while(T--) 82 { 83 scanf("%d%d%d",&n,&m,&k); 84 for(int i=1;i<=m;i++) 85 for(int j=1;j<=m;j++) 86 mapp[i][j]=1; 87 for(int i=1;i<=k;i++) 88 { 89 scanf("%d%d",&t1,&t2); 90 mapp[t1][t2]=mapp[t2][t1]=0; 91 } 92 printf("%d ",Solve(n)); 93 } 94 return 0; 95 }