POJ2888 Magic Bracelet

题目传送门

分析：

首先我们看到某两种珠子不能相邻，考虑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
",ans*ksm(n,MOD-2)%MOD);
    }
}