Tóm tắt đề bài

Đếm số lượng dây chuyền (vòng tròn) gồm \(n\) viên ngọc, mỗi viên có \(m\) màu. Hai dây chuyền được xem là giống nhau nếu có thể xoay (quay vòng) để trùng khớp. Hãy in số lượng dây chuyền khác nhau modulo \(10^9+7\).

Phân tích

• Nếu xét như một dãy độ dài \(n\) thì có \(m^n\) cách tô màu, nhưng do phép xoay tạo ra các cấu hình tương đương nên cần chia theo nhóm đối xứng.
• Bài toán chính là đếm số quỹ đạo của tập các tô màu dưới tác động của nhóm quay \(C_n\) (gồm \(n\) phép quay).

• Dùng Định lý Burnside:

  • Số cấu hình khác nhau (theo quay) bằng trung bình số cấu hình bất biến theo mỗi phép quay.

• Với phép quay dịch \(k\) vị trí (với \(0 \le k < n\)):

  • Các vị trí được chia thành \(\gcd(n,k)\) chu trình.
  • Để tô màu bất biến sau khi quay, tất cả phần tử trong cùng một chu trình phải cùng màu.
  • Do đó số tô màu bất biến là \(m^{\gcd(n,k)}\).

Vậy đáp án:

• Vì modulo \(10^9+7\) là số nguyên tố, ta tính \(\frac{1}{n}\) bằng nghịch đảo modular \(n^{-1} \equiv n^{\text{mod}-2}\).

Hướng giải quyết

Nhận xét

• Phép quay \(k\) chỉ ảnh hưởng qua giá trị \(g=\gcd(n,k)\).
• Code AC đang triển khai trực tiếp công thức Burnside:
  • Duyệt \(k = 0 \dots n-1\)
  • Cộng \(m^{\gcd(n,k)}\)
  • Nhân với \(n^{-1}\) modulo.

Thuật toán

1. Đọc \(n, m\).
2. Khởi tạo ans = 0.
3. Với mỗi \(k\) từ \(0\) đến \(n-1\):
   • Tính \(g = \gcd(n,k)\)
   • Cộng vào ans giá trị \(m^g \bmod mod\) bằng lũy thừa nhanh.
4. Tính ans = ans * inverse(n) % mod.
5. In ans.

Các bẫy thường gặp

• Quên rằng phép quay \(k\) tạo \(\gcd(n,k)\) chu trình (không phải \(n/\gcd\)).
• Chia cho \(n\) trong modulo phải dùng nghịch đảo modular, không dùng chia thường.
• Cần lũy thừa nhanh để tính \(m^g\).

Độ phức tạp

• Thời gian: \(O(n \log n)\) (vì mỗi lần tính \(m^{\gcd}\) bằng lũy thừa nhanh \(O(\log n)\), lặp \(n\) lần).
• Bộ nhớ: \(O(1)\).

Code tham khảo

#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename _Tp> bool minimize(_Tp &__a, const _Tp &__b) { if (__a > __b) { __a = __b; return true; } return false; }
template <typename _Tp> bool maximize(_Tp &__a, const _Tp &__b) { if (__a < __b) { __a = __b; return true; } return false; }

const int mod = 1e9 + 7;

// Tính x^n mod mod bằng lũy thừa nhanh (đệ quy)
int quick_pow(int x, int n) {
    if (n == 0) {
        return 1;
    }

    int t = quick_pow(x, n / 2);
    t = (ll)t * t % mod;

    if (n % 2 == 0) {
        return t;
    }
    return (ll)t * x % mod;
}

// Nghịch đảo modulo theo Fermat: x^(mod-2) mod mod (mod là số nguyên tố)
int inverse(int x) {
    return quick_pow(x, mod - 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int ans = 0;

    // Burnside: ans = (1/n) * sum_{k=0..n-1} m^{gcd(k,n)}
    rep (i, 0, n - 1) {
        (ans += quick_pow(m, __gcd(i, n))) %= mod;
    }

    ans = (ll)ans * inverse(n) % mod;
    cout << ans << "\n";
    return 0;
}