题目传送门
分析：
首先我们看到某两种珠子不能相邻，考虑dp
dp[ i ][ j ]表示串了 i 个，最后一个珠子为 j 的方案数。。
这个东西可以矩阵加速来算
可以连在一起的设为1，否则为0
然后我们直接使用polya定理大力统计
但是N很大，O(nlogn)直接求gcd会T
于是考虑一些奇奇怪怪的操作
我们尝试枚举可能出现的gcd，显然只有可能是N的因子
其次这个gcd会作出多少次贡献呢？
我们考虑gcd(i,N)=x
那么i/x肯定与N/x互质
那么贡献就是φ( N/x )
复杂度O( N^1/2 * m^3 * log N )
有点卡常，由于MOD很小，少模几次就过了
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<string> #include<iostream> #define maxn 1000005 #define maxm 15 #define MOD 9973 #define INF 0x3f3f3f3f using namespace std; inline long long getint() { long long num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=num*10+c-48,c=getchar(); return num*flag; } int n,m; int pri[maxn],np[maxn],cnt; struct node{ long long a[maxm][maxm]; friend node operator *(node x,node y) { node z; for(int i=1;i<=m;i++)for(int j=1;j<=m;j++) { z.a[i][j]=0; for(int k=1;k<=m;k++)z.a[i][j]+=x.a[i][k]*y.a[k][j]; z.a[i][j]%=MOD; } return z; } }A,I; inline void init() { for(int i=2;i<maxn;i++) { if(!np[i])pri[++cnt]=i; for(int j=1;j<=cnt&&i*pri[j]<maxn;j++) { np[i*pri[j]]=1; if(i%pri[j]==0)break; } } for(int i=1;i<=10;i++)I.a[i][i]=1; } inline node ksm(node num,long long k) { node ret=I; for(;k;k>>=1,num=num*num)if(k&1)ret=ret*num; return ret; } inline long long ksm(long long num,long long k) { long long ret=1; for(;k;k>>=1,num=num*num%MOD)if(k&1)ret=ret*num%MOD; return ret; } inline long long phi(int num) { int tmp=num; for(int i=1;pri[i]*pri[i]<=num;i++) if(num%pri[i]==0) { tmp=tmp/pri[i]*(pri[i]-1); while(num%pri[i]==0)num/=pri[i]; } if(num>1)tmp=tmp/num*(num-1); return tmp; } inline long long getans(int k) { node tmp=ksm(A,k); long long num=0; for(int i=1;i<=m;i++)num+=tmp.a[i][i]; return num%MOD; } int main() { int T=getint(); init(); while(T--) { n=getint(),m=getint(); int tmp=getint(); long long ans=0; for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)A.a[i][j]=1; while(tmp--) { int u=getint(),v=getint(); A.a[u][v]=A.a[v][u]=0; } for(int i=1;i*i<=n;i++)if(n%i==0) { if(i*i==n)(ans+=getans(i)*phi(i))%=MOD; else (ans+=getans(i)*phi(n/i)+getans(n/i)*phi(i))%=MOD; } printf("%lld\n",ans*ksm(n,MOD-2)%MOD); } }