题解：P12142 [蓝桥杯 2025 省 A] 黑客

Kagamino_Natsumi · 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;
}