1 条题解
-
0
解题分析与代码实现
题目重述
哈利需要制作一个由颗魔法珠子组成的圆形手镯,有种不同的珠子。其中对珠子不能相邻。求不考虑旋转同构的不同手镯数量,结果对取模。
约束条件
- 禁止相邻的珠子对可能不对称
解题方法
核心算法
- Burnside引理:处理旋转对称性
- 矩阵快速幂:计算固定旋转角度下的合法排列数
- 欧拉函数:计算与旋转角度相关的系数
关键步骤
- 构建转移矩阵,其中表示类珠子可以接类
- 对于每个,计算:
- 长度为的合法线性排列数(矩阵的迹)
- 乘以欧拉函数
- 根据Burnside引理求平均值
代码实现
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; const int MOD = 9973; const int MAXN = 65540; const int MAT_SIZE = 15; bool is_prime[MAXN]; int prime[MAXN], len; int T, N, M, K; struct Matrix { int n; int mat[MAT_SIZE][MAT_SIZE]; void clear() { memset(mat, 0, sizeof(mat)); } void Init() { clear(); for(int i = 1; i <= n; ++i) mat[i][i] = 1; } friend Matrix operator*(const Matrix &a, const Matrix &b) { Matrix c; c.n = a.n; c.clear(); for(int i = 1; i <= a.n; ++i) for(int j = 1; j <= a.n; ++j) for(int k = 1; k <= a.n; ++k) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k]*b.mat[k][j]) % MOD; return c; } friend Matrix operator^(Matrix a, int x) { Matrix res; res.n = a.n; res.Init(); while(x) { if(x & 1) res = res * a; a = a * a; x >>= 1; } return res; } }A; // 预处理素数表 void InitPrimes() { len = 0; memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; prime[len++] = 2; for(int i = 4; i < MAXN; i += 2) is_prime[i] = false; for(int i = 3; i*i <= MAXN; i += 2) { if(is_prime[i]) { prime[len++] = i; for(int j = i*i; j < MAXN; j += i) is_prime[j] = false; } } for(; i < MAXN; ++i) if(is_prime[i]) prime[len++] = i; } // 计算欧拉函数 int euler(int n) { int ret = n; for(int i = 0; i < len && (long long)prime[i]*prime[i] <= n; ++i) { if(n % prime[i] == 0) { ret = ret / prime[i] * (prime[i] - 1); while(n % prime[i] == 0) n /= prime[i]; } } if(n > 1) ret = ret / n * (n - 1); return ret % MOD; } // 计算长度为x的合法排列数 int cal(int x) { Matrix a = A^x; int ans = 0; for(int i = 1; i <= a.n; ++i) ans = (ans + a.mat[i][i]) % MOD; return ans; } // 快速幂模运算 int power_mod(int a, int b) { int ret = 1; a %= MOD; while(b) { if(b & 1) ret = (ret * a) % MOD; a = (a * a) % MOD; b >>= 1; } return ret; } int main() { InitPrimes(); scanf("%d", &T); while(T--) { scanf("%d %d %d", &N, &M, &K); // 初始化转移矩阵 A.n = M; for(int i = 1; i <= M; ++i) for(int j = 1; j <= M; ++j) A.mat[i][j] = 1; // 设置禁止相邻的对 while(K--) { int u, v; scanf("%d %d", &u, &v); A.mat[u][v] = A.mat[v][u] = 0; } // Burnside引理计算 int ans = 0; for(int i = 1; i*i <= N; ++i) { if(N % i == 0) { if(i*i == N) { ans = (ans + cal(i)*euler(i)) % MOD; } else { ans = (ans + cal(i)*euler(N/i) + cal(N/i)*euler(i)) % MOD; } } } // 乘以N的逆元 ans = ans * power_mod(N, MOD-2) % MOD; printf("%d\n", ans); } return 0; }
- 1
信息
- ID
- 1889
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者