题目分析

我们需要计算用 $m$ 种颜色给所有 $n$ 个点的 symmetric labeled clique 染色的方案数。

理解 symmetric labeled clique

一个 symmetric labeled clique 满足：

1. 所有连通分量大小相同（设为 $k$）
2. 每个连通分量都是完全图 $K_k$

这意味着图的结构由 $k$ 唯一确定，其中 $k$ 是 $n$ 的因子。图由 $\frac{n}{k}$ 个不相交的 $K_k$ 组成。

重新理解染色对象

关键：题目说"将每个元素染色"，这里的"元素"指的是所有的 symmetric labeled clique。也就是说：

• 我们有一个集合 $S$，包含所有 $n$ 个点的 symmetric labeled clique
• 我们要用 $m$ 种颜色给 $S$ 中的每个图染色
• 两种方案不同当且仅当存在某个图被染成不同颜色

这等价于：从 $S$ 到颜色集合 $\{1,2,\dots,m\}$ 的所有映射，即 $m^{|S|}$。

所以问题转化为：计算 $n$ 个点的 symmetric labeled clique 的数量，然后求 $m^{|S|} \bmod (10^9-401)$。

计算 symmetric labeled clique 的数量

第一步：固定分量大小 $k$

设每个连通分量大小为 $k$，则 $k$ 必须是 $n$ 的因子。图由 $\frac{n}{k}$ 个 $K_k$ 组成。

第二步：计算固定 $k$ 时的图数量

对于 $n$ 个标号顶点，将它们划分为 $\frac{n}{k}$ 个大小为 $k$ 的组，每组内部形成完全图：

1. 分组方案数：将 $n$ 个不同元素分成 $\frac{n}{k}$ 个无标号组，每组 $k$ 个元素：

   $$\frac{n!}{(k!)^{\frac{n}{k}} \cdot (\frac{n}{k})!} $$

2. 每组内部边确定：每个组内部已经是完全图，无需选择

所以对于固定的 $k$，图的数量为：

$$f(k) = \frac{n!}{(k!)^{\frac{n}{k}} \cdot (\frac{n}{k})!} $$

第三步：对所有因子求和

设 $d_1, d_2, \dots, d_r$ 是 $n$ 的所有正因子，则：

$$|S| = \sum_{k \mid n} f(k) = \sum_{k \mid n} \frac{n!}{(k!)^{\frac{n}{k}} \cdot (\frac{n}{k})!} $$

最终答案

答案为：

$$\text{ans} = m^{|S|} \bmod (10^9-401)$$

其中 $10^9-401 = 999999599$ 是一个质数。

算法实现要点

1. 因子分解：对 $n$ 进行质因数分解，生成所有正因子
2. 模数运算：使用快速幂计算 $m^{|S|} \bmod 999999599$
3. 大数处理：$n, m$ 最大到 $2\times 10^9$，需要注意：
   • 阶乘计算会很大，但 $|S|$ 本身不会超过 $2\times 10^9$
   • 实际上 $|S|$ 是 $n$ 的因子个数个项的和，不会太大

样例验证

对于 $n=4, m=2$：

$n=4$ 的因子：1, 2, 4

• $k=1$：$f(1) = \frac{4!}{(1!)^4 \cdot 4!} = 1$
• $k=2$：$f(2) = \frac{4!}{(2!)^2 \cdot 2!} = \frac{24}{4 \cdot 2} = 3$
• $k=4$：$f(4) = \frac{4!}{(4!)^1 \cdot 1!} = 1$

$|S| = 1 + 3 + 1 = 5$

答案 = $2^5 = 32$，与样例一致。

核心代码框架

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 999999599;  // 10^9 - 401

// 快速幂
ll pow_mod(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 获取n的所有因子
vector<ll> get_divisors(ll n) {
    vector<ll> divisors;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    return divisors;
}

// 计算阶乘 (实际只需要计算到n，但n可能很大)
// 这里需要预计算或使用其他方法，但注意n最大2e9
// 实际上我们只需要计算f(k)的值，需要处理大数阶乘比大小

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m;
        
        vector<ll> divisors = get_divisors(n);
        ll set_size = 0;
        
        // 这里需要计算每个f(k)并累加
        // 注意：实际实现中需要处理大数运算
        for (ll k : divisors) {
            // 计算f(k) = n! / ( (k!)^(n/k) * (n/k)! )
            // 由于n可能很大，需要特殊处理
            set_size += calculate_f(n, k); // 需要实现这个函数
        }
        
        ll ans = pow_mod(m, set_size, MOD);
        cout << ans << endl;
    }
    return 0;
}

复杂度分析

• 因子个数：$O(\sqrt{n})$，最多约 $10^3$ 量级
• 主要复杂度在于计算 $f(k)$，需要高效计算大数组合数
• 总体在合理范围内

总结

本题的关键在于理解"给所有 symmetric labeled clique 染色"的含义，将其转化为计算这种图的数量，然后求幂。组合计数部分需要仔细处理标号图的分划计数。