题目描述
Ginny 的生日马上就来了。魔法大叔 Herry 准备给他的新妹子一个生日礼物。礼物是由 N 个魔法珠子串成的魔法手镯。每种不同种类的珠子有其独一无二的特性。Herry 的另一个妹子远坂凛指出，有一些指定种类的成对珠子，如果挨在一块会发生化学反应甚至核聚变，因此 Herry 必须非常小心以确保这些珠子不会相邻。
Herry想知道，究竟能有多少不同的手镯，将这个结果 mod 9973 并告诉他。注意，若一个手镯能够通过旋转得到另一个手镯，我们将这两个手镯视为相同的。
输入格式
输入包含多组数据。第一行一个正整数 case ，为数据的组数。
接下来的数据分为 case 组，每一组的第一行为三个正整数 N,M,K ， N 为珠子的数量，M 为珠子的种类数， K 为不能相邻的种类对数，保证 N≢0 (mod 9973)
接下来 K 行每行两个正整数 i,j，表示种类 i 的珠子不能和种类 j 的珠子相邻。
1≤case≤10 , 1≤N≤109 , 1≤M≤10
Burnside引理裸题，另外要求满足一定限定条件的 n 个珠子有多少种方案，f[i][j] 表示第一个放 i 当前这个放 j 的方案数， dp转移用矩阵乘法加速一下即可。
#include<bits/stdc++.h> typedef long long ll; const int P = 9973; int Case, n, m, k, u, v, d[(int)1e5]; struct matrix{ int a[11][11]; }; matrix e, full; matrix operator * (const matrix &a, const matrix &b) { matrix c; memset(&c, 0, sizeof(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] += a.a[i][k] * b.a[k][j]; c.a[i][j] %= P; } return c; } matrix pow(matrix x, int k) { matrix ret = e; for (; k; k >>= 1, x = x * x) if (k & 1) ret = ret * x; return ret; } int phi(int x) { int ret = x; for (int i=2; i * i <= x; i++) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } ll pow(ll x, int k) { ll ret = 1; for (; k; k >>= 1, x = x * x % P) if (k & 1) ret = ret * x % P; return ret; } ll inv (ll x) {return pow(x, P - 2);} int main() { scanf("%d", &Case); for (int i=1; i <= 10; i++) e.a[i][i] = 1; for (int i=1; i <= 10; i++) for (int j=1; j <= 10; j++) full.a[i][j] = 1; while (Case--) { scanf("%d%d%d", &n, &m, &k); matrix tra = full; while (k--) scanf("%d%d", &u, &v), tra.a[u][v] = 0, tra.a[v][u] = 0; matrix cp = tra; ll ans = 0; int kind = 0; for (int i=1; i * i <= n; i++) if (n % i == 0) d[++kind] = i, d[++kind] = n / i; if (kind >= 2 && d[kind] == d[kind - 1]) kind--; for (int k=1; k <= kind; k++) if (n % d[k] == 0) { matrix f = e * pow(tra, n / d[k] - 1); ll tans = 0; for (int i=1; i <= m; i++) for (int j=1; j <= m; j++) if (cp.a[i][j]) tans += f.a[i][j]; ans = (ans + tans * phi(d[k])); } printf("%lld\n", ans * inv(n) % P); } return 0; }