C++(g++ 7.5.0) 解法, 执行用时: 104ms, 内存消耗: 464K, 提交时间: 2023-06-08 19:51:15

#include <iostream>
#include <algorithm>
#include <cstring>

using i64 = long long;

using namespace std;

const int mod = 9973, N = 11;

int n, m, k;

struct Matrix {
    int v[N][N];
    
    Matrix (int t = 0) {
        memset(v, 0, sizeof v);
        if (t == 1)
            for (int i = 0; i < m; i++)
                v[i][i] = 1;
    }
    
    Matrix operator*(const Matrix& b) const {
        Matrix res;
        for (int k = 0; k < m; k++)
            for (int i = 0; i < m; i++)
                for (int j = 0; j < m; j++)
                    (res.v[i][j] += this->v[i][k] * b.v[k][j] % mod) %= mod;
        return res;
    }
    
    Matrix operator^(int b) {
        Matrix res = 1, a = *this;
        while (b) {
            if (b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
} trans;


int qpow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}

int phi(int x) {
  int res = x;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      res = res / i * (i - 1);
    }
  }
  if (x > 1) res = res / x * (x - 1);
  return res;
}

int f(int n) {
  int res = 0;
  for (int i = 0; i < m; i++) {
    Matrix ori;
    ori.v[0][i] = 1;
    ori = ori * (trans ^ (n - 1));
    for (int j = 0; j < m; j++) {
      if (trans.v[i][j]) {
        (res += ori.v[0][j]) %= mod;
      }
    }
  }
  return res;
}

int calc(int n) {
  int res = 0;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res = (res + 1ll * phi(i) * f(n / i) % mod) % mod;
      if (i * i != n) {
        res = (res + 1ll * phi(n / i) * f(i) % mod) % mod;
      }
    }
  }
  return 1ll * res * qpow(n, mod - 2) % mod;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < m; j++)
        trans.v[i][j] = 1;
    for (int i = 1; i <= k; i++) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      trans.v[u][v] = trans.v[v][u] = 0;
    }
    cout << calc(n) << '\n';
  }
  return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 460K, 提交时间: 2022-01-11 14:38:30

#include<cstdio>
#include<cstring>
const int mod = 9973;
int n,m,k,ans,d[3005],phi[3005],cnt;
struct Mat{
    int s[10][10];
    Mat(){memset(s,0,sizeof s);}
    void unit(){memset(s,0,sizeof s);for(int i=0;i<m;i++) s[i][i]=1;}
    Mat operator * (const Mat &B)const{
        Mat ret;
        for(int k=0;k<m;k++)
            for(int i=0;i<m;i++) if(s[i][k])
                for(int j=0;j<m;j++) if(B.s[k][j])
                    ret.s[i][j]+=s[i][k]*B.s[k][j];
        for(int i=0;i<m;i++) for(int j=0;j<m;j++) ret.s[i][j]%=mod;
        return ret;
    }
}f,g,G;
inline void Add(int x,int t){
    int now=cnt;
    for(int i=1;i<=now;i++){
        d[++cnt]=d[i]*x,phi[cnt]=phi[i]*(x-1);
        for(int k=2;k<=t;k++) d[cnt+1]=d[cnt]*x,phi[cnt+1]=phi[cnt]*x,cnt++;
    }
}
inline int MatPow(int N){
    f.unit(),g=G;
    for(;N;N>>=1,g=g*g) if(N&1) f=f*g;
    int ret=0;
    for(int i=0;i<m;i++) ret+=f.s[i][i];
    return ret%mod;
}
inline int Pow(int a,int b){int s=1;for(;b;b>>=1,a=a*a%mod) if(b&1) s=s*a%mod;return s;}
int main()
{
    scanf("%*d");
    while(~scanf("%d%d%d",&n,&m,&k)){
        ans=0,d[cnt=1]=1,phi[1]=1;
        int x=n,y,t;
        for(int i=2;i*i<=x;i++) if(x%i==0){t=0;while(x%i==0) x/=i,t++;Add(i,t);}
        if(x>1) Add(x,1);
        for(int i=0;i<m;i++) for(int j=0;j<m;j++) g.s[i][j]=1;
        for(int i=1;i<=k;i++) scanf("%d%d",&x,&y),x--,y--,g.s[x][y]=g.s[y][x]=0;
        G=g;
        for(int i=1;i<=cnt;i++) ans=(ans+1ll*phi[i]*MatPow(n/d[i]))%mod;
        printf("%d\n",ans*Pow(n%mod,mod-2)%mod);
    }
}