Blog

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11, P = 9973;
int m;
struct MATRIX {
    int a[N][N];
    MATRIX() { memset(a, 0, sizeof a); }
}; 
MATRIX operator*(MATRIX a, MATRIX b) {
    MATRIX c;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= m; k++)
                c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % P;
    return c;
}
int qmi(MATRIX a, int b) {
    MATRIX res;
    // 初始化矩阵
    for (int i = 1; i <= m; i++) res.a[i][i] = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a, b >>= 1;
    }
    // 算对角线答案
    int sum = 0;
    for (int i = 1; i <= m; i++) sum += res.a[i][i];
    return sum;
}
int phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res % P;
}
int inv(int n) {
    n %= P;
    for (int i = 1; i < P; i++)
        if (i * n % P == 1) return i;
    return -1;
}
int main() {
    int T, n, k;
    cin >> T;
    while (T-- && cin >> n >> m >> k) {
        MATRIX tr;
        // 构造矩阵
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                tr.a[i][j] = 1;
        for (int x, y; k-- && cin >> x >> y; ) 
            tr.a[x][y] = tr.a[y][x] = 0;
        // 枚举 n 的约数算答案
        int res = 0;
        for (int i = 1; i <= n / i; i++) 
            if (n % i == 0) {
                res = (res + qmi(tr, i) * phi(n / i)) % P;
                if (i != n / i) 
                    res = (res + qmi(tr, n / i) * phi(i)) % P;
            }
        // 结尾别忘除以 n
        cout << res * inv(n) % P << endl;
    }
    return 0;
}