CF2040F Number of Cubes

滑不拉稽 · 2024-12-12 02:42:14 · 题解

回顾 burnside 引理。对于一个群 G 和群 G 作用下的状态空间集合 X，能得到的本质不同的状态数量等于：

即 G 中各个元素的不动点数量的平均数。

对于本题，G 中的元素可以表示为三元组 \{(x, y, z)\mid a\in[0,a),b\in[0,b),c\in[0,c)\}，代表向三个方向移动的步数，|G|=abc。

那么对于 g=(x,y,z)\in G，不动点的个数即有多少个三维数组（即立方体）A 满足：

• \forall i \in [0,a),j\in[0,b),l\in[0,c)$，$A_{i,j,l}=A_{(i+x)\bmod a,(j+y)\bmod b,(l+z)\bmod c}

思考这个问题并不容易，可以先思考简单的情况：

给定正整数 x，有多少个长为 n 的序列 A 满足 \forall i\in [0,n)，A_i=A_{(i+x)\bmod n}？

手填一下会发现满足条件的序列的循环节长为 \gcd(x,n)，一共有 T=\frac{n}{\gcd(x,n)} 个循环节。

一样使用 k 种颜色涂色，由每个循环节的内容相同，得出满足颜色 i 出现 d_i 次的必要条件是 \forall i\in [1,k]，T\mid d_i。

在此基础上，每个循环节可以分到 \dfrac{d_i}{T} 个颜色 i。那么给单个循环节涂色的方案数 col_T 就是：

回到到三维的情况，不难想象对于动作 g=(x,y,z)\in G，此时的循环节数量就是每一维循环节数量的最小公倍数，即：

这意味着循环节只和动作本身有关，而在这个立方体的哪一个点上施加这个动作得到的循环节数量都是相同的。

至此，我们有了一个单组数据 O(a\cdot b\cdot c\cdot k) 的解法：三层循环遍历 G 中的元素，对于每一个 g\in G，计算出循环节个数 T，这样不动点的个数就是用给定数目的颜色染单个循环节的方案数 col_T。

因为 a\cdot b\cdot c \le 3\cdot 10^6 是对单组数据而言的，所以考虑把 a\cdot b \cdot c 优化掉。由于 \frac{a}{\gcd(a,x)}\mid a，可以转化为枚举 a 的因数，那么对于 a 的一个因数 h，需要计算有多少个 x\in[0,a) 满足 \frac{a}{\gcd(a,x)}=h。不妨令 p=\gcd(a,x)，则 \gcd(\frac{a}{p},\frac{x}{p})=\gcd(h,\frac{x}{p})=1。又 \frac{x}{p}<\frac{a}{p}=h，故满足条件的 x 的个数是 < h 且和 h 互素的数的个数，即 \varphi(h)。

故最终的做法是用三层循环枚举 a,b,c 的因数，分别记为 f_a,f_b,f_c，并计算出循环节个数 T = \text{lcm}(f_a,f_b,f_c)。若循环节个数 T 整除所有的 d_i（即整除所有 d_i 的 \gcd），答案就累加上 col_T\cdot\varphi(f_a)\cdot\varphi(f_b)\cdot\varphi(f_c)。

时间复杂度 O(T(\sigma(w)\cdot k+\sigma(abc)\cdot\log a))。其中 \sigma 是因数个数函数，w 是所有 d_i 的 \gcd。

void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;

    vector<int> d(k);
    int A = 0;
    for (int i = 0; i < k; i++) {
        cin >> d[i];
        A = gcd(A, d[i]);
    }

    vector<mint> f(A + 1);
    auto calc = [&] (int T) {
        f[T] = 1;
        mint all = a * b * c / T;
        for (auto x : d) {
            f[T] *= C(all, x / T);
            all -= x / T;
        }
    };
    for (int i = 1; i * i <= A; i++) {
        if (A % i == 0) {
            calc(i);
            calc(A / i);
        }
    }

    auto getd = [&] (int x, vector<int> &vec) {
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                vec.push_back(i);
                if (i * i < x) {
                    vec.push_back(x / i);
                }
            }
        }
    };
    vector<int> da, db, dc;
    getd(a, da);
    getd(b, db);
    getd(c, dc);

    mint ans = 0;
    for (auto x : da) {
        for (auto y : db) {
            for (auto z : dc) {
                int T = lcm(x, lcm(y, z));
                if (A % T == 0) {
                    ans += f[T] * phi[x] * phi[y] * phi[z];
                }
            }
        }
    }
    ans /= a * b * c;
    cout << ans << "\n";
}