本文主要是介绍POJ 2888 Magic Bracelet(ploya)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
跟POJ2154一样的思路，但是这题多了个颜色限制
构造关系矩阵，每次有i个循环节，就做i次矩阵乘法，得到的就是每个颜色经过i步能回到自身的情况数，利用矩阵快速幂就可以快速计算了
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int MOD = 9973;int t, n, m, k;struct Mat {int v[11][11];Mat() {memset(v, 0, sizeof(v));}Mat operator * (Mat c) {Mat ans;for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < m; k++) {ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j]) % MOD;}}}return ans;}
};int phi(int n) {int ans = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {ans = ans / i * (i - 1);while (n % i == 0) n /= i;}}if (n > 1) ans = ans / n * (n - 1);return ans % MOD;
}int cal(Mat A, int k) {Mat ans;for (int i = 0; i < m; i++)ans.v[i][i] = 1;while (k) {if (k&1) ans = ans * A;A = A * A;k >>= 1;}int out = 0;for (int i = 0; i < m; i++)out = (out + ans.v[i][i]) % MOD;return out;
}int pow_mod(int x, int k) {x %= MOD;int ans = 1;while (k) {if (k&1) ans = ans * x % MOD;x = x * x % MOD;k >>= 1;}return ans;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d%d", &n, &m, &k);int u, v;Mat A;for (int i = 0; i < m; i++)for (int j = 0; j < m; j++)A.v[i][j] = 1;while (k--) {scanf("%d%d", &u, &v);A.v[u - 1][v - 1] = 0;A.v[v - 1][u - 1] = 0;}int ans = 0;for (int i = 1; i * i <= n; i++) {if (n % i == 0) {ans = (ans + phi(n / i) * cal(A, i)) % MOD;if (n / i != i) {int tmp = n / i;ans = (ans + phi(n / tmp) * cal(A, tmp)) % MOD;}}}printf("%d\n", ans * pow_mod(n, MOD - 2) % MOD);}return 0;
}
这篇关于POJ 2888 Magic Bracelet(ploya)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
