POJ-2888 Magic Bracelet（Burnside引理+矩阵优化+欧拉函数+逆元）

Burnside引理经典好题呀！

题解参考 https://blog.****.net/maxwei_wzj/article/details/73024349#commentBox 这位大佬的。

这题时间卡得很紧，注意矩阵乘法不能太多次取模，不然会TLE。   因为这题的模数是9973，加完之后再取模也不会炸。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1e6+;
const int MOD=;
int n,m,k,tot=;

struct matrix{
    int m[][];
    matrix() { memset(m,,sizeof(m)); }
    friend matrix operator*(matrix a,matrix b) {
        matrix res;
        for (int i=;i<=;i++) for (int j=;j<=;j++) {
            for (int k=;k<=;k++) res.m[i][j]=res.m[i][j]+a.m[i][k]*b.m[k][j];
            res.m[i][j]%=MOD;  //少取模不然会TLE
        }
        return res;
    }
};

bool vis[N]; int pri[N];
void prework(int n) {
    memset(vis,false,sizeof(vis));  //vis为0素数  1和数
    for (int i=;i<=n;i++){
        if (!vis[i]) pri[++tot]=i;
        for (int j=;j<=tot&&i*pri[j]<=n;j++){
            vis[i*pri[j]]=;
            if (i%pri[j]==) break;
        }
    }
}

int power(int x,int p) {
    int ret=; x%=MOD;
    for (;p;p>>=) {
        if (p&) ret=(ret*x)%MOD;
        x=(x*x)%MOD;
    }
    return ret;
}

int phi(int n) {
    int ret=n;
    for (int i=;i<=tot && pri[i]<=sqrt((double)n);i++)
        if (n%pri[i]==) {
            ret=ret/pri[i]*(pri[i]-);
            while (n%pri[i]==) n/=pri[i];
        }
    if (n>) ret=ret/n*(n-);
    return ret%MOD;
}

int count(matrix A,int p) {  //计算B=A^p  然后返回sigma(B[i][i])
    matrix B;
    for (int i=;i<=m;i++) B.m[i][i]=;
    for (;p;p>>=) {
        if (p&) B=B*A;
        A=A*A;
    }
    int ret=;
    for (int i=;i<=m;i++) ret=(ret+B.m[i][i])%MOD;
    return ret;
}

//POJ-2888 由n(n <= 10^9)个珠子组成的项链，每个珠子共有m(m <= 10)种颜色，再给定k组限制(a, b)表示颜色a和颜色b的珠子不能相邻，问总共有多少种方案满足长度为n的项链。
//题解：Burnside引理 + 矩阵优化 + 欧拉函数 + 逆元。
int main()
{
    prework();
    int T; cin>>T;
    while (T--) {
        scanf("%d%d%d",&n,&m,&k);

        matrix A;  //可达矩阵（类似图论）
        for (int i=;i<=k;i++) {
            int x,y; scanf("%d%d",&x,&y);
            A.m[x][y]=A.m[y][x]=;
        }
        for (int i=;i<=m;i++) for (int j=;j<=m;j++) A.m[i][j]=-A.m[i][j];

        int ans=;
        for (int i=;i*i<=n;i++)
            if (n%i==) {
                ans=(ans+count(A,i)*phi(n/i)%MOD)%MOD;
                if (i*i!=n) ans=(ans+count(A,n/i)*phi(i)%MOD)%MOD;
            }
        cout<<ans*power(n,MOD-)%MOD<<endl;
    }
    return ;
}