POJ2888 Magic Bracelet

Time Limit: 2000MS		Memory Limit: 131072K
Total Submissions: 5476		Accepted: 1775

Description

Ginny’s birthday is coming soon. Harry Potter is preparing a birthday present for his new girlfriend. The present is a magic bracelet which consists of n magic beads. The are m kinds of different magic beads. Each kind of beads has its unique characteristic. Stringing many beads together a beautiful circular magic bracelet will be made. As Harry Potter’s friend Hermione has pointed out, beads of certain pairs of kinds will interact with each other and explode, Harry Potter must be very careful to make sure that beads of these pairs are not stringed next to each other.

There infinite beads of each kind. How many different bracelets can Harry make if repetitions produced by rotation around the center of the bracelet are neglected? Find the answer taken modulo 9973.

Input

The first line of the input contains the number of test cases.

Each test cases starts with a line containing three integers n (1 ≤ n ≤ 10⁹, gcd(n, 9973) = 1), m (1 ≤ m ≤ 10), k (1 ≤ k ≤ m(m − 1) ⁄ 2). The next k lines each contain two integers a and b (1 ≤ a, b ≤ m), indicating beads of kind a cannot be stringed to beads of kind b.

Output

Output the answer of each test case on a separate line.

Sample Input

Sample Output

Source

POJ Monthly--2006.07.30, cuiaoxiang

数学问题统计 burnside引理矩阵乘法乘法逆元

求旋转同构下不同的染色方案，有某两种颜色不能放在相邻位置的要求。

旋转同构时，同一个循环节里只能填相同的颜色，若有k个循环节，可以看做是走一条1->2->3->..->k->1的回路，其中每个位置可以选一种颜色。

似乎可以转化成图论中的路径条数问题。

建出邻接矩阵，若两种颜色可以相邻，就“连边”。邻接矩阵自乘k次后，对角线元素累加起来就是当前状况下的方案数。

最后div n需要用到乘法逆元

  1 #include<cstdio>  
  2 #include<cstring>  
  3 #include<algorithm>  
  4 using namespace std;  
  5 const int MOD = 9973;  
  6 typedef long long LL;  
  7 int m,k,n,a,b,T,mat[10][10],tmp[10][10],tp[10][10],prime[36000],is[36000];  
  8 void getprime()  
  9 {  
 10     int cnt=0;  
 11     for(int i=2;i<36000;i++)  
 12     {  
 13         if(!is[i])  
 14         {  
 15             prime[cnt++]=i;  
 16             for(int j=i;j<36000;j+=i)  
 17                 is[j]=1;  
 18         }  
 19     }  
 20 }  
 21 int pow(int x,int y)  
 22 {  
 23     x=x%MOD;  
 24     int t=1;  
 25     while(y)  
 26     {  
 27         if(y&1)t=(t*x)%MOD;  
 28         x=(x*x)%MOD;  
 29         y>>=1;  
 30     }  
 31     return t;  
 32 }  
 33 void mul(int a[10][10],int b[10][10],int m)  
 34 {  
 35     int c[10][10];  
 36     memset(c,0,sizeof(c));  
 37     for(int i=0;i<m;i++)  
 38         for(int j=0;j<m;j++)  
 39             for(int k=0;k<m;k++)  
 40                 c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;  
 41     for(int i=0;i<m;i++)  
 42         for(int j=0;j<m;j++)  
 43             a[i][j]=c[i][j];  
 44 }  
 45 int get(int x)  
 46 {  
 47     memset(tmp,0,sizeof(tmp));  
 48     for(int i=0;i<m;i++)  
 49         for(int j=0;j<m;j++)  
 50             tp[i][j]=mat[i][j];  
 51     for(int i=0;i<m;i++)tmp[i][i]=1;  
 52     while(x)          
 53     {  
 54         if(x&1)  
 55             mul(tmp,tp,m);  
 56         mul(tp,tp,m);  
 57         x>>=1;  
 58     }  
 59     int ans=0;  
 60     for(int i=0;i<m;i++)  
 61         ans=(ans+tmp[i][i])%MOD;  
 62     return ans;  
 63 }  
 64 int eular(int x)  
 65 {  
 66     if(x==1)return 1;  
 67     int rep=x;  
 68     for(int i=0;prime[i]*prime[i]<=x;i++)  
 69     {  
 70         if(x%prime[i]==0)  
 71         {  
 72             rep-=rep/prime[i];  
 73             x/=prime[i];  
 74         }  
 75         while(x%prime[i]==0)x/=prime[i];  
 76         if(x==1)break;  
 77     }  
 78     if(x!=1)  
 79         rep-=rep/x;  
 80     return rep%MOD;  
 81 }  
 82 int inv(int n)  
 83 {  
 84     return pow(n,MOD-2)%MOD;  
 85 }  
 86 int main()  
 87 {  
 88     scanf("%d",&T);  
 89     getprime();  
 90     while(T--)  
 91     {  
 92         scanf("%d%d%d",&n,&m,&k);  
 93         for(int i=0;i<m;i++)  
 94             for(int j=0;j<m;j++)  
 95                 mat[i][j]=1;  
 96         for(int i=0;i<k;i++)  
 97         {  
 98             scanf("%d%d",&a,&b);  
 99             a--;  
100             b--;  
101             mat[a][b]=mat[b][a]=0;  
102         }  
103         int ans=0;  
104         int i;  
105         for(i=1;i*i<n;i++)  
106         {  
107             if(n%i==0)  
108             {  
109                 ans=(ans+(get(i)*eular(n/i))%MOD)%MOD;  
110                 ans=(ans+(get(n/i)*eular(i))%MOD)%MOD;  
111             }  
112         }  
113         if(i*i==n)  
114             ans=(ans+(get(i)*eular(n/i))%MOD)%MOD;  
115         printf("%d
",(ans*inv(n))%MOD);  
116     }  
117     return 0;  
118 }