1 条题解

  • 0
    @ 2025-5-22 21:20:17

    解题分析与代码实现

    题目重述

    哈利需要制作一个由nn颗魔法珠子组成的圆形手镯,有mm种不同的珠子。其中kk对珠子不能相邻。求不考虑旋转同构的不同手镯数量,结果对99739973取模。

    约束条件

    • 1n1091 ≤ n ≤ 10^9
    • 1m101 ≤ m ≤ 10
    • gcd(n,9973)=1\gcd(n, 9973) = 1
    • 禁止相邻的珠子对可能不对称

    解题方法

    核心算法

    1. Burnside引理:处理旋转对称性
    2. 矩阵快速幂:计算固定旋转角度下的合法排列数
    3. 欧拉函数:计算与旋转角度相关的系数

    关键步骤

    1. 构建转移矩阵AA,其中Aij=1A_{ij}=1表示ii类珠子可以接jj
    2. 对于每个dnd|n,计算:
      • 长度为dd的合法线性排列数(矩阵AdA^d的迹)
      • 乘以欧拉函数ϕ(n/d)\phi(n/d)
    3. 根据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
    上传者