CF2040F Number of Cubes
原题链接：F. Number of Cubes
Tag：数论、计数、Burnside引理
题目描述
假设存在一个边长为 \(a\)、\(b\)、\(c\) 的长方体， 这个长方体由 \(k\) 种不同颜色的单位立方体组成， 我们可以在这个立方体的三个方向上进行任意次数的循环平移。
现在有 \(d_i\) 个单位立方体的颜色为 \(i(1 \leq i \leq k)\)。这些立方体可以组成多少个长方体， 其中没有任何两个长方体可以经过某种循环平移的方案而相等。
数据说明：
\(1 \leq a,b,c \leq 3 \cdot 10^6\)
\(a \cdot b \cdot c \leq 3 \cdot 10^6\)
\(1 \leq k \leq 10^6\)
\(1 \leq d_1 \leq d_2 \leq \cdots \leq d_k \leq 3 \cdot 10^6\)
分析
先回顾一下 \(\text{Burnside}\) 引理求轨道数的形式： \(\frac{1}{|G|}\sum\limits_{g\in G}|X^g|\)。
在这个问题里，我们可以把循环平移这个操作看成置换 \(|G|\)，我们将置换作用于这个长方体上，故 \(X\) 表示了这个长方体。
那么这个 \(|G|\) 是容易求解的，因为题目中没有给定具体平移操作是怎样的，但是给定了长方体的长宽高， 因此我们可以想到，不同的平移方案数量有 \(a \times b \times c\) 种。
我们用以下形式来表示一种置换 \(g = (a',b',c')\) 表示在 \(a\) 方向上平移了 \(a'\) 个单位， \(b\) 方向上平移了 \(b'\) 个单位，\(c\) 方向上平移了 \(c'\) 个单位。
假设我们已经确定了一种置换，那么这个置换的循环节是多少？ 我们先考虑一个维度上的情况， 在 \(a\) 方向上的每次移动 \(a'\) 个单位， 则循环节为 \(\displaystyle\frac{a}{\gcd(a,a')}\)。 \(b\) 与 \(c\) 方向上的同理，分别为 \(\displaystyle\frac{b}{\gcd(b,b')}\) 与 \(\displaystyle\frac{c}{\gcd(c,c')}\)。 那么综合三维的循环节就是 \(\displaystyle\lcm(\frac{a}{\gcd(a,a')},\frac{b}{\gcd(b,b')},\frac{c}{\gcd(c,c')})\)。 我们将这个循环周期命名为 \(T\)。
在这个时候我们可以得出一组 \((a',b',c')\) 对答案产生的贡献为 \(\displaystyle\binom{\frac{abc}{T}}{\frac{d_1}{T}} \times \binom{\frac{abc}{T} - \frac{d_1}{T}}{\frac{d_2}{T}} \times \binom{\frac{abc}{T} - \frac{d_1}{T} - \frac{d_2}{T}}{\frac{d_3}{T}} \cdots\) 其中 \(T|d_1,T|d_2,\cdots,T|d_k\)。
这个时候已经存在一个枚举 \(a,b,c\) 的做法了，但是由于数据范围， 这个做法显然是要超时的，接下来我们考虑如何优化做法。
上述做法中存在两个潜在的优化方案，第一个是我们可以发现我们实际上能取到的 \(T\) 是非常有限的， 因此我们可以先求一个 \(G = \gcd(d_1,d_2,\cdots,d_k)\)， 而 \(T\) 能取到的值就是 \(G\) 的因子，这部分是很容易预处理出来的。
虽然上述优化有一部分效果，但是复杂度的重要组成 \(abc\) 还没有被优化掉， 于是我们思考第二个潜在的优化方案， 由于 \(\displaystyle\frac{a}{\gcd(a,a')} | a\)， 我们可以发现，既然枚举 \([1,a]\) 是不可接受的， 那么我们可以转而枚举 \(a\) 的所有因子。 假设我们对于一个 \(a\) 的因子 \(y\)， 我们需要找到在 \([0,a)\) 这个范围里有多少个数字 \(x\) 满足 \(\displaystyle\frac{a}{\gcd(a,x)} = y\)， 我们将这里的 \(\displaystyle\frac{a}{\gcd(a,x)}\) 记作 \(z\)， 那么就可以得到 \(\gcd(y , \frac{x}{z}) = 1\)， 又因为我们知道 \(\displaystyle\frac{x}{z} \lt y\)， 所以我们要找的满足条件的 \(x\) 的个数， 其实就是满足小于 \(y\) 的同时和 \(y\) 互质的数字个数， 上面这句话是欧拉函数的定义 \(\varphi(y)\)。 因此我们可以用筛线性求欧拉函数，最后在统计答案时， 我们直接枚举 \(a,b,c\) 的因子，之后用其因子的欧拉函数进行统计答案。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int Welcome24ever = 0;
#define endl '\n'
#define fixset(x) fixed << setprecision(x)
#define int long long
typedef pair<int, int> PII;
const int MOD = 998244353;
const int N = 3e6 + 5;
int p[N],vis[N],cnt,phi[N];
void get_phi(int n){
phi[1] = 1;
for(int i = 2;i <= n;i++){
if(!vis[i]){
p[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0;i * p[j] <= n;j++){
int m = i * p[j];
vis[m] = 1;
if(i % p[j] == 0){
phi[m] = p[j] * phi[i];
break;
}else phi[m] = (p[j] - 1) * phi[i];
}
}
}
int fastPow(int a,int n) {
int ans = 1;
a %= MOD;
while (n) {
if (n & 1)
ans = (ans * a) % MOD;
a = (a * a) % MOD;
n >>= 1;
}
return ans;
}
int inv(int x) {
return fastPow(x, MOD - 2);
}
int fac[N],ifc[N];
int C(int n, int m) {
return fac[n] * ifc[n - m] % MOD * ifc[m] % MOD;
}
void NeverSayNever() {
int a, b, c, k; cin >> a >> b >> c >> k;
vector<int> d(k);
int G = 0;
for (auto &x: d) cin >> x;
for (auto &x: d) G = gcd(x, G);
vector<int> div;
for (int i = 1; i * i <= G; i++) {
if (G % i == 0) {
div.push_back(i);
div.push_back(G / i);
}
}
vector<int> tmp(G + 1);
for (auto &T: div) {
tmp[T] = 1;
int all = a * b * c / T;
for (auto x: d) {
tmp[T] *= C(all, x / T);
tmp[T] %= MOD;
all -= x / T;
}
}
auto work = [&](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> ad, bd, cd;
work(a,ad);
work(b,bd);
work(c,cd);
int ans = 0;
for (auto &x: ad) {
for (auto &y: bd) {
for (auto &z: cd) {
int L = lcm(lcm(x, y), z);
if (G % L == 0) {
ans += tmp[L] * phi[x] * phi[y] * phi[z];
ans %= MOD;
}
}
}
}
ans *= inv(a * b * c);
cout << ans % MOD << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
cin >> T;
get_phi(N);
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
ifc[N-1]=inv(fac[N-1]);
for (int i=N-1;i;i--) ifc[i-1]=ifc[i]*i%MOD;
while (T--) {
NeverSayNever();
}
return Welcome24ever;
}
日志
本页面创建于 2025/1/18 18:45
特别鸣谢：
Kilo_5723推荐此题和指导。