本文涉及知识点

组合数学汇总
数论：质数、最大公约数、菲蜀定理
C++图论

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

题目描述

蓝桥王国拥有 $42$ 座城市以及 $42$ 位骑士。这些骑士按照 $1$ 到 $42$ 的编号顺序，分别居住在对应编号的城市中。即第 $1$ 位骑士居住在城市 $1$，第 $2$ 位骑士居住在城市 $2$，依此类推。

最近，王国中引入了一项革命性技术：空间传送装置。该装置可以根据一个长度为 $42$ 的数字排列 $a$，将所有骑士一次性传送至新的城市。

排列 $a$ 必须由 $1\sim 42$ 共 $42$ 个数字组成，且每个数字只出现一次。在传送操作中，位于城市 $i$（$i=1,2,3,\cdots ,42$）的骑士会被传送到城市 $a_i$。例如，如果 $a_1$ 的值为 $3$，那么当前位于城市 $1$ 的骑士会被传送至城市 $3$。

为测试技术的可靠性，王国决定连续 $2024$ 天每天使用同一排列 $a$ 进行一次传送操作。

小蓝负责为这次测试设计排列 $a$，她的目标是确保所有骑士在经过 $2024$ 天传送后，都能返回自己的起始城市。而在此之前的任何一天，不会出现所有骑士都回到起始城市的情况。

请问，有多少种不同的数字排列 $a$ 能满足小蓝的需求？由于答案可能很大，因此你只需要将答案对 $10^9+7$ 取模后提交即可。

数字排列 $a$ 是由 $1$ 到 $42$ 这 $42$ 个数字按照一定顺序排列而成的序列。每个数字在排列中只能出现一次，且所有数字必须全部包含在排列中。

如果两个排列中至少有一个位置上的数字不同，则这两个排列被视为不同的数字排列。例如， { 1 , 2 , 3 , ⋯   , 42 } \{1, 2, 3, \cdots, 42\} {1,2,3,⋯,42} 和 { 1 , 3 , 2 , ⋯   , 42 } \{1, 3, 2, \cdots, 42\} {1,3,2,⋯,42} 就是不同的数字排列，因为它们在第二个位置上的数不相同。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

图论 数论 组合数学

令任何合法组合是P,增加42条有向边$i\to P[i]$，构成有向图G，G的每个连通区域有如下性质。
性质一：各点入度和出度都为1。
性质二：出度都为1，点数有限，故一定存在环。
性质三：出度为1，故进入环后无法离开。即环上任意一点不会直接或间接指向非环上一点。
性质四：不互存在非环上一点，指向当前环。所有边反向，结合性质三，再反向。
性质五：两个环不会相交，否则和出度1矛盾。
结论一：每个联通区域都是一个环。
2024天后，所有骑士都到达初始位置。2024是所有环长的公倍数。
之前的任何一天，不会出现所有骑士都回到起始城市的情况。2024是所有环长的最小公倍数。
$2024=2\times 2\times 2\times 11\times 23$
所有环长之和是42。
必定有环的长度是$23\times i$,由于环长之和是42，故$23\times i\le 42$,故i只能取值1。即一定有环长为23。
$11\times i+23\le 42$，故i只能是1，故一定存在环位11。
余下的环长度之和是8,必定是8的倍数。故必定存在环长为8。
一，第一步为环长8选择8个点,不考虑顺序。
二，第二步为环11选择11个点,不考虑顺序。
共19个点，方案数：$\frac{42!}{8!\times 11!\times 23!}$
三，为三个环选择边。
环长x边的方案数：
$(x-1)!$ 以任意点开始，第二个点有x-1中选择，第三个点有x-2种选择$\cdots$
故答案是： $\frac{42!}{8!\times 11!\times 23!}\times 7!\times 10!\times 22!=\frac{42!}{8\times 11\times 23}$

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};

template<long long MOD = 1000000007, class T1 = int, class T2 = long long>
class C1097Int
{
public:
	C1097Int(T1 iData = 0) :m_iData(iData% MOD)
	{

	}
	C1097Int(T2 llData) :m_iData(llData% MOD) {

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((T2)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((T2)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = ((T2)MOD + m_iData - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)const
	{
		return C1097Int(((T2)MOD + m_iData - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((T2)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((T2)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this *= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(T2 n)const
	{
		C1097Int iRet = (T1)1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	T1 ToInt()const
	{
		return ((T2)m_iData + MOD) % MOD;
	}
private:
	T1 m_iData = 0;;
};
template<class T >
class CFactorial
{
public:
	CFactorial(int n) :m_res(n + 1) {
		m_res[0] = 1;
		for (int i = 1; i <= n; i++) {
			m_res[i] = m_res[i - 1] * i;
		}
	}
	T Com(int iSel, int iCanSel)const {
		return m_res[iCanSel] / m_res[iSel] / m_res[iCanSel - iSel];
	}
	T Com(const vector<int>& cnt)const {
		T biRet = 1;
		int iCanSel = std::accumulate(cnt.begin(), cnt.end(), 0);
		for (int j = 0; j < cnt.size(); j++) {
			biRet *= Com(cnt[j], iCanSel);
			iCanSel -= cnt[j];
		}
		return biRet;
	}
	vector<T> m_res;
};
class Solution {
public:
	int Ans2024() {
		typedef C1097Int<> BI;
		CFactorial<BI> fac(42);
		BI ans = fac.m_res.back() / 8 / 11 / 23;
		return ans.ToInt();
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	ios::sync_with_stdio(0); cin.tie(nullptr);
	//CInBuff<> in; COutBuff<10'000'000> ob;	
	/*int N,M;
	cin >> N >> M;
	auto A = Read<int>(N);
	auto P = Read<double>(M);*/
#ifdef _DEBUG	
		//printf("N=%d", N);
		//Out(A, ",A=");
		//Out(P, ",P=");
		/*Out(edge, ",edge=");		
		Out(que, ",que=");*/
	   //Out(ab, ",ab=");
	   //Out(par, "par=");
	   //Out(que, "que=");
	   //Out(B, "B=");
#endif // DEBUG	
	auto res = Solution().Ans2024();
		printf("%d", res);
	return 0;
};

单元测试

	TEST_METHOD(TestMethod1)
		{			
			auto res = Solution().Ans2024();
			AssertEx(151495483, res);
		}

# 扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。