题解：P12286 [蓝桥杯 2024 国 Java A] 空间传送装置

· · 题解

题目大意：找到长度为 42 的排列 a，使得 a 的最小正周期为2024，即 a 可以被分解为若干个循环，这些循环的长度的最小公倍数为 2024。

解题思路：首先，为了使循环长度的最小公倍数为 2024 且长度和为 42，那么循环长度必须是 2024 小于 42 因数，包括：1，2，4，8，11，22，23,所以排列 a 如果要使其长度和为 42，就必须由长度为 8，11 和 23 的循环组成。

想必到这里就非常简单了，不就是一个简单的排列组合问题吗？我们可以选择 8 个位置来形成长度为 8 的循环，有 \binom{42}{8} 种选择方式。从剩下的 34 个位置中选择 11 个位置来形成长度为 11 的循环，有 \binom{34}{11} 种选择方式。最后，剩下的 23 个位置自然形成长度为 23 的循环，有 \binom{23}{23}=1 种选择方式。

最后，因为对于每个长度为 k 的循环，有 (k-1)! 种不同的排列方式。因此，长度为 8 的循环有 7! 种排列方式，长度为 11 的循环有 10! 种排列方式，长度为 23 的循环有 22! 种排列方式。

综上所述，答案即为：

\left(\binom{42}{8}\times\binom{34}{11}\times 7!\times 10!\times 22!\right)\bmod(10^9+7)

自己口算一下提交即可。