专栏文章

CF2040F Number of Cubes

滑滑不拉稽
CF2040F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqt5i7r
此快照首次捕获于
2025/12/04 10:19
3 个月前
此快照最后确认于
2025/12/04 10:19
3 个月前
查看原文
回顾 burnside 引理。对于一个群 GG 和群 GG 作用下的状态空间集合 XX，能得到的本质不同的状态数量等于：
1∣G∣∑g∈G∑x∈X[gx=x]\frac{1}{|G|}\sum_{g\in G}\sum_{x\in X}[gx=x]
即 GG 中各个元素的不动点数量的平均数。
对于本题，GG 中的元素可以表示为三元组 {(x,y,z)∣a∈[0,a),b∈[0,b),c∈[0,c)}\{(x, y, z)\mid a\in[0,a),b\in[0,b),c\in[0,c)\}，代表向三个方向移动的步数，∣G∣=abc|G|=abc。
那么对于 g=(x,y,z)∈Gg=(x,y,z)\in G，不动点的个数即有多少个三维数组（即立方体）AA 满足：
  • ∀i∈[0,a),j∈[0,b),l∈[0,c)\forall i \in [0,a),j\in[0,b),l\in[0,c)，Ai,j,l=A(i+x) mod a,(j+y) mod b,(l+z) mod cA_{i,j,l}=A_{(i+x)\bmod a,(j+y)\bmod b,(l+z)\bmod c}
  • ∀i∈[1,k]\forall i\in [1,k]，cnti=dicnt_i=d_i，其中 cnticnt_i 是颜色 ii 在 AA 中出现的次数。
思考这个问题并不容易，可以先思考简单的情况：
给定正整数 xx，有多少个长为 nn 的序列 AA 满足 ∀i∈[0,n)\forall i\in [0,n)，Ai=A(i+x) mod nA_i=A_{(i+x)\bmod n}？
手填一下会发现满足条件的序列的循环节长为 gcd⁡(x,n)\gcd(x,n)，一共有 T=ngcd⁡(x,n)T=\frac{n}{\gcd(x,n)} 个循环节。
一样使用 kk 种颜色涂色，由每个循环节的内容相同，得出满足颜色 ii 出现 did_i 次的必要条件是 ∀i∈[1,k]\forall i\in [1,k]，T∣diT\mid d_i。
在此基础上，每个循环节可以分到 diT\dfrac{d_i}{T} 个颜色 ii。那么给单个循环节涂色的方案数 colTcol_T 就是：
(abcTd1T)(abcT−d1Td2T)(abcT−d1T−d2Td3T)⋯\binom{\frac{abc}{T}}{\frac{d_1}{T}} \binom{\frac{abc}{T}-\frac{d_1}{T}}{\frac{d_2}{T}} \binom{\frac{abc}{T}-\frac{d_1}{T}-\frac{d_2}{T}}{\frac{d_3}{T}}\cdots
回到到三维的情况，不难想象对于动作 g=(x,y,z)∈Gg=(x,y,z)\in G，此时的循环节数量就是每一维循环节数量的最小公倍数，即：
lcm(agcd⁡(a,x),bgcd⁡(b,y),cgcd⁡(c,z))\text{lcm}(\frac{a}{\gcd(a,x)},\frac{b}{\gcd(b,y)},\frac{c}{\gcd(c,z)})
这意味着循环节只和动作本身有关，而在这个立方体的哪一个点上施加这个动作得到的循环节数量都是相同的。
至此，我们有了一个单组数据 O(a⋅b⋅c⋅k)O(a\cdot b\cdot c\cdot k) 的解法：三层循环遍历 GG 中的元素，对于每一个 g∈Gg\in G，计算出循环节个数 TT，这样不动点的个数就是用给定数目的颜色染单个循环节的方案数 colTcol_T。
因为 a⋅b⋅c≤3⋅106a\cdot b\cdot c \le 3\cdot 10^6 是对单组数据而言的，所以考虑把 a⋅b⋅ca\cdot b \cdot c 优化掉。由于 agcd⁡(a,x)∣a\frac{a}{\gcd(a,x)}\mid a，可以转化为枚举 aa 的因数，那么对于 aa 的一个因数 hh，需要计算有多少个 x∈[0,a)x\in[0,a) 满足 agcd⁡(a,x)=h\frac{a}{\gcd(a,x)}=h。不妨令 p=gcd⁡(a,x)p=\gcd(a,x)，则 gcd⁡(ap,xp)=gcd⁡(h,xp)=1\gcd(\frac{a}{p},\frac{x}{p})=\gcd(h,\frac{x}{p})=1。又 xp<ap=h\frac{x}{p}<\frac{a}{p}=h，故满足条件的 xx 的个数是 <h< h 且和 hh 互素的数的个数，即 φ(h)\varphi(h)。
故最终的做法是用三层循环枚举 a,b,ca,b,c 的因数，分别记为 fa,fb,fcf_a,f_b,f_c，并计算出循环节个数 T=lcm(fa,fb,fc)T = \text{lcm}(f_a,f_b,f_c)。若循环节个数 TT 整除所有的 did_i（即整除所有 did_i 的 gcd⁡\gcd），答案就累加上 colT⋅φ(fa)⋅φ(fb)⋅φ(fc)col_T\cdot\varphi(f_a)\cdot\varphi(f_b)\cdot\varphi(f_c)。
时间复杂度 O(T(σ(w)⋅k+σ(abc)⋅log⁡a))O(T(\sigma(w)\cdot k+\sigma(abc)\cdot\log a))。其中 σ\sigma 是因数个数函数，ww 是所有 did_i 的 gcd⁡\gcd。
C
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";
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...