自动搬运

查看原文

来自洛谷，原作者为

	Kagamino_Natsumi 友跨 | 代词使用TA/其 | 音游 | 轨道交通 | XCPC | 福建三本黑子 | 为永夜城的黎明而战

搬运于2025-08-24 23:13:05，当前版本为作者最后更新于2025-04-13 02:15:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12142 [蓝桥杯 2025 省 A] 黑客

第一次参加蓝桥杯，可以说题目言简意赅，质量还是不错的。虽然最后两道题分别因为精度和忽略情况而喜提 WA

思路

本题给出了打乱顺序的 $n \times m + 2$ 个数。为了方便统计，自然需要对这些数据排序。本题中，矩阵中数字的大小其实没有什么作用，只需要统计其个数，而且数据范围为 $1 \leq a_i \leq 5 \times 10^{5}$ ，非常适合使用计数排序。

矩阵的长和宽都必须在题目给出的 $n \times m + 2$ 个数之中，只需要一一枚举矩阵的可能长宽即可。注意，在每次枚举长和宽进行统计时，都需要把长和宽从计数中去掉，以免重复统计。

每次统计的过程如下：对矩阵中全部的 $n \times m$ 个数进行全排列，共有 $(n \times m)！$ 种方案。其中，若有重复的 $x$ 个数，则这 $x$ 个数无论怎么排列都是同一种方案，需要在总方案数上除以 $x！$ 。注意模意义下的除法需要使用逆元。

多次求阶乘及逆元的过程十分耗时，可以提前进行预处理。

时间复杂度为 $O(a_{max}^{1.5} )$。

Code

#include<bits/stdc++.h>
using namespace std;

int sum;
int scale;
int x;
long long bucket[500007];
long long jc[500007] = {1};
long long invjc[500007] = {};
long long ans = 0;
const long long mod = 1000000007ll;

long long qpow(long long a, long long b)
{
	long long res = 1;
	while(b)
	{
		if(b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1; 
	}
	return res;
}

long long inv(long long x)
{
	return qpow(x, mod - 2);
}

int main()
{
	cin >> sum;
	scale = sum - 2;
	for(long long i = 1; i <= 500000; i++)
	{
		jc[i] = jc[i - 1] * i % mod;
	}
	for(int i = 0; i <= 500000; i++)
	{
		invjc[i] = inv(jc[i]);
	}
	for(int i = 1; i <= sum; i++)
	{
		cin >> x;
		bucket[x]++;
	}
	for(int i = 1; i <= scale; i++)
	{
		if(scale % i == 0 && bucket[i] && bucket[scale / i])
		{
			int n = i, m = scale / i;
			bucket[n]--;
			bucket[m]--;
			long long now = jc[scale];
			for(int j = 1; j <= 500000; j++)
				if(bucket[j])
					now = now * invjc[bucket[j]] % mod;
			ans = (ans + now) % mod;
			bucket[n]++;
			bucket[m]++;
		}
	}
	cout << ans << endl;
	return 0;
}