这是一道 CF 2040F - Number of Cubes 的题解。
下面给出详细分析。

---

题目大意

有一个 $a \times b \times c$ 的长方体，由单位立方体组成，共有 $k$ 种颜色，颜色 $i$ 有 $d_i$ 个立方体（$\sum d_i = a \cdot b \cdot c$）。

我们可以对长方体在三个方向上分别进行循环移位（类似魔方平移）。

问：本质不同的长方体有多少个？
这里的“本质不同”是指不能通过若干次循环移位相互转化。

答案对 $998244353$ 取模。

---

核心思路

这是典型的 Burnside 引理（Polya 计数） 问题。

1. 群作用

操作群 $G$ 由所有三方向循环移位组成：

$$G = \{ (i, j, l) \mid 0 \le i < a,\ 0 \le j < b,\ 0 \le l < c \} $$

总操作数 $|G| = a \cdot b \cdot c$。

---

2. Burnside 引理

本质不同的长方体数：

$$\frac{1}{|G|} \sum_{g \in G} \text{Fix}(g)$$

其中 $\text{Fix}(g)$ 是在操作 $g$ 下保持不变的着色方案数。

---

3. 循环分解

对于一个固定操作 $(i,j,l)$，考虑它在长方体上的作用。
将每个立方体坐标 $(x,y,z)$（$0 \le x < a,\ 0 \le y < b,\ 0 \le z < c$）移动 $i$ 步在 $x$ 方向、$j$ 步在 $y$ 方向、$l$ 步在 $z$ 方向，形成若干轨道（循环）。

可以证明：所有循环的长度相等，且为：

$$N = \mathrm{lcm}\left( \frac{a}{\gcd(a,i)},\ \frac{b}{\gcd(b,j)},\ \frac{c}{\gcd(c,l)} \right) $$

这是因为每个方向上的循环长度分别为 $\frac{a}{\gcd(a,i)}$ 等，总的循环长度是它们的最小公倍数。

---

4. 不动点条件

一个着色在操作 $(i,j,l)$ 下不变，当且仅当每个循环内的所有立方体颜色相同。

因此：

• 每个颜色数量 $d_t$ 必须能被 $N$ 整除（因为每个循环需要 $N$ 个同色立方体）
• 方案数 = 将 $\frac{d_t}{N}$ 个“循环组”分配给 $k$ 种颜色的多重组合数：

$$\text{Fix}(g) = \frac{\left( \sum_{t=1}^k \frac{d_t}{N} \right)!}{\prod_{t=1}^k \left( \frac{d_t}{N} \right)!} $$

---

5. 优化：按 $N$ 分组

直接枚举所有 $a \cdot b \cdot c$ 个操作不可行（太大）。
注意到 $N$ 一定是 $a \cdot b \cdot c$ 的约数，而且由 $\gcd$ 的比值决定。

设：

$$x = \frac{a}{\gcd(a,i)},\quad y = \frac{b}{\gcd(b,j)},\quad z = \frac{c}{\gcd(c,l)} $$

则 $x \mid a$，$y \mid b$，$z \mid c$，且 $N = \mathrm{lcm}(x,y,z)$。

---

6. 计算给定 $(x,y,z)$ 的操作数

固定 $x$，需要 $i$ 满足 $\frac{a}{\gcd(a,i)} = x$。

等价于 $\gcd(a,i) = \frac{a}{x}$。
设 $d = \frac{a}{x}$，则 $i$ 必须是 $d$ 的倍数，且 $\gcd(a/d,\ i/d) = 1$，即 $i/d$ 与 $a/d$ 互质，且 $1 \le i/d \le x$。

因此满足条件的 $i$ 的个数为 $\varphi(x)$（欧拉函数）。

同理对 $y,z$。

所以三元组 $(x,y,z)$ 对应的操作数 = $\varphi(x) \cdot \varphi(y) \cdot \varphi(z)$。

---

7. 预处理所有约数的欧拉函数

用筛法预处理范围内所有数的欧拉函数。
然后枚举 $x \mid a$，$y \mid b$，$z \mid c$，计算 $N = \mathrm{lcm}(x,y,z)$，累积计数。

---

8. 合并相同 $N$

由于 $N$ 很小（$a\cdot b\cdot c \le 3\cdot 10^6$），我们可以用 DP 或直接枚举约数组合来计算每个 $N$ 的总操作数 cnt[N]。

---

9. 多重组合数计算

对于每个 $N$，如果所有 $d_t$ 都能被 $N$ 整除，则

• 令 $m_t = d_t / N$
• 总循环数 $M = \sum m_t = \frac{a\cdot b\cdot c}{N}$
• 多重组合数 = $\frac{M!}{\prod m_t!}$

标程中直接用 MC(u) 计算。

---

10. 最终答案

$$\text{ans} = \frac{1}{a b c} \sum_{N} \text{cnt}[N] \cdot \text{multinomial}(d_1/N,\dots,d_k/N) $$

对 $998244353$ 取模，除法用逆元。

---

标程代码注释版

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];  // 将约数映射到压缩下标

int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        } else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}

int inv(int a) { return powmod(a, mod - 2); }

void prepare() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = (fact[i-1] * i) % mod;
    ifact[N-1] = inv(fact[N-1]);
    for (int i = N-2; i >= 0; i--) ifact[i] = (ifact[i+1] * (i+1)) % mod;
}

int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n-k]) % mod;
}

// 多重组合数： ∑a 个物品分成给定数量
int MC(vector<int>& a) {
    int sum = 0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) res = (res * ifact[i]) % mod;
    return res;
}

int lcm(int a, int b) { return a / __gcd(a, b) * b; }

vector<int> all_divs(int x) {
    vector<int> d1, d2;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d1.push_back(i);
            if (i * i != x) d2.push_back(x / i);
        }
    }
    reverse(d2.begin(), d2.end());
    for (int i : d2) d1.push_back(i);
    return d1;
}

void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector<int> v(k);
    for (int& i : v) cin >> i;

    // 所有 di 的最大公约数
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
    vector<int> divs_g = all_divs(g);

    // 收集所有需要用到的约数（a,b,c,g 的约数）
    set<int> divs;
    for (int i : all_divs(a)) divs.insert(i);
    for (int i : all_divs(b)) divs.insert(i);
    for (int i : all_divs(c)) divs.insert(i);
    for (int i : all_divs(g)) divs.insert(i);
    int D = divs.size();
    int idx = 0;
    for (int j : divs) pos[j] = idx++;

    // cnt[t][pos] = 满足 a_t / gcd(a_t, i) = 该约数的 i 的个数
    vector<vector<int>> tmp(3, vector<int>(D));
    vector<vector<int>> cnt(3, vector<int>(D));
    for (int t = 0; t < 3; t++) {
        int x = (t == 0 ? a : (t == 1 ? b : c));
        vector<int> divs_x = all_divs(x);
        for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
            tmp[t][pos[divs_x[i]]] += x / divs_x[i];
            for (int j = 0; j < i; j++) {
                if (divs_x[i] % divs_x[j] == 0) {
                    tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
                }
            }
            cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
        }
    }

    // DP: dp[i][pos] 表示考虑了 i 个维度，当前 lcm = 该约数的方案数
    vector<vector<int>> dp(4, vector<int>(D));
    dp[0][0] = 1;  // 空乘积的 lcm 为 1
    for (int i = 0; i < 3; i++) {
        for (int t1 : divs_g) {
            for (int t2 : divs_g) {
                int new_lcm = lcm(t1, t2);
                dp[i+1][pos[new_lcm]] = (dp[i+1][pos[new_lcm]]
                    + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
            }
        }
    }

    int ans = 0;
    for (int N : divs) {
        if (g % N != 0) continue;
        int ways = dp[3][pos[N]];
        if (ways == 0) continue;
        vector<int> u;
        for (int t : v) u.push_back(t / N);
        ans = (ans + MC(u) * ways) % mod;
    }

    ans = ans * inv(a * b * c) % mod;
    cout << ans << "\n";
}

int32_t main() {
    prepare();
    int tt;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

---

复杂度分析

• 预处理欧拉函数相关：$O(\max(a,b,c) \log \log \max)$
• 对每个测试，枚举约数组合：$O(d(a) \cdot d(b) \cdot d(c) \cdot \log C)$
• 多重组合数计算：$O(k)$
• 总复杂度可接受，因为 $a\cdot b\cdot c \le 3\cdot 10^6$，约数数量少。

---

总结

本题是 Polya 计数的高阶应用，核心在于：

1. 用 Burnside 引理转化为求不动点。
2. 循环长度 $N = \mathrm{lcm}\left(\frac{a}{\gcd(a,i)},\dots\right)$。
3. 用欧拉函数统计每个 $(x,y,z)$ 对应的操作数。
4. 按 $N$ 分组计算多重组合数。
5. 最终除以 $|G| = abc$。