根据题意,需要交换的部分会形成若干个不相交的环,独立处理每个环。
每个环可以用环内的最小值去和其它元素交换,或者用全局最小值和环上最小值交换,做一遍再交换回去。
#include <cstdio> #include <cstring> const int MOD = 9973; int m, n, k; void M(int &a) { if (a >= MOD) a -= MOD; if (a < 0) a += MOD; } struct Mat { int mat[11][11]; void clear() { memset(mat, 0, sizeof(mat)); } Mat(int x = 0) { memset(mat, 0, sizeof(mat)); for (int i = 1; i <= m; i++) mat[i][i] = x; } Mat operator * (const Mat &p) const { Mat c; for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) { int cnt = 0; for (int k = 1; k <= m; k++) cnt += mat[i][k] * p.mat[k][j]; c.mat[i][j] = cnt % MOD; } return c; } Mat operator ^ (int b) { Mat c(1); Mat a = *this; while (b) { if (b & 1) c = c * a; a = a * a; b >>= 1; } return c; } } base, res; int phi(int n) { int ans = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { ans -= ans / i; while (n % i == 0) n /= i; } } if (n > 1) ans -= ans / n; return ans % MOD; } int qp(int a, int b = MOD - 2) { int ans = 1; a %= MOD; while (b) { if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } int solve(int x) { res = base ^ x; int ans = 0; for (int i = 1; i <= m; i++) M(ans += res.mat[i][i]); return ans; } int solve() { int ans = 0; for (int i = 1; i * i <= n; i++) { if (n % i) continue; M(ans += 1LL * phi(n / i) * solve(i) % MOD); if (i * i == n) continue; M(ans += 1LL * phi(i) * solve(n / i) % MOD); } return ans * qp(n) % MOD; } int main() { int T; scanf("%d", &T); while (T--) { base.clear(); scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) base.mat[i][j] = 1; while (k--) { int a, b; scanf("%d%d", &a, &b); base.mat[a][b] = base.mat[b][a] = 0; } printf("%d\n", solve()); } return 0; }View Code