题目描述

给定 $L = n \times m + 2$ 个打乱顺序的正整数 $a_1, a_2, \dots, a_L$。这些数原本包含矩阵的行数 $n$、列数 $m$，以及 $n \times m$ 个矩阵元素。我们需要找出，可能有多少种不同的原始 $n \times m$ 矩阵。两个矩阵相同，当且仅当它们的行数、列数以及每个对应位置上的元素都相同。结果对 $1000000007$ 取模。

样例

输入:
6
2 2 1 4 3 3

输出:
24

样例说明

输入的 6 个数是 2, 2, 1, 4, 3, 3。总数 $L=6$。
矩阵元素个数 $k = L - 2 = 4$。
我们需要从输入的 6 个数中选出两个作为 $n$ 和 $m$，使得 $n \times m = 4$。

可能的 $(n, m)$ 组合及对应的矩阵元素：
1. 选择 $n=1, m=4$：
* 输入中没有 1 和 4。无法构成。等等，样例解释说可以？ “There are 6 possible original matrices: (2, 2, 3, 3), …” 这里的 (2, 2, 3, 3) 是指矩阵元素，不是 n, m。
* 重新理解：是从打乱的序列中选择两个数，它们的值分别是 $n$ 和 $m$。
* 考虑序列 {2, 2, 1, 4, 3, 3}。
* Case 1: 选出 $n=1, m=4$。这两个数本身必须在序列中。序列中有 1 和 4。
* 取出一对 (1, 4)。剩余的数是 {2, 2, 3, 3}。这些是 $1 \times 4 = 4$ 个矩阵元素。
* 将 {2, 2, 3, 3} 排列成 $1 \times 4$ 的矩阵。有多少种不同的排列？这是多重集排列问题。总共 4 个元素，其中 2 有 2 个，3 有 2 个。排列数为 $\frac{4!}{2!2!} = \frac{24}{2 \times 2} = 6$。
* Case 2: 选出 $n=4, m=1$。
* 取出一对 (4, 1)。剩余的数是 {2, 2, 3, 3}。这些是 $4 \times 1 = 4$ 个矩阵元素。
* 将 {2, 2, 3, 3} 排列成 $4 \times 1$ 的矩阵。排列数同样是 $\frac{4!}{2!2!} = 6$。
* Case 3: 选出 $n=2, m=2$。
* 需要取出两个 2。序列中有两个 2。
* 取出一对 (2, 2)。剩余的数是 {1, 4, 3, 3}。这些是 $2 \times 2 = 4$ 个矩阵元素。
* 将 {1, 4, 3, 3} 排列成 $2 \times 2$ 的矩阵。有多少种不同的排列？总共 4 个元素，其中 1 有 1 个，4 有 1 个，3 有 2 个。排列数为 $\frac{4!}{1!1!2!} = \frac{24}{1 \times 1 \times 2} = 12$。

总计可能的矩阵数量 = 6 + 6 + 12 = 24。

算法 (组合数学 + 计数)

$O(L \log L + D \log \max(a_i))$ 或 $O(L + V + D)$

思路分析

1. 问题核心:
   我们需要从给定的 $L$ 个数的多重集 (multiset) 中，选择两个数作为矩阵的维度 $n$ 和 $m$，同时满足 $n \times m = k = L - 2$。剩下的 $k$ 个数则作为矩阵的元素。对于每一种有效的 $(n, m)$ 选择和对应的 $k$ 个元素的多重集，我们需要计算这 $k$ 个元素可以构成多少个不同的 $n \times m$ 矩阵。最后将所有情况的矩阵数量加起来。

2. 计数矩阵排列:
   假设我们确定了一对维度 $(n, m)$ 使得 $n \times m = k = L-2$，并且我们确定了构成矩阵的 $k$ 个元素的多重集 $M$。
   多重集 $M$ 中包含了各种数值及其出现的次数。设数值 $v$ 在 $M$ 中出现了 $c_v$ 次，且 $\sum c_v = k$。
   将这 $k$ 个元素填入 $n \times m$ 的矩阵中，不同的填充方式（即不同的矩阵）的数量等于这 $k$ 个元素的全排列数，但需要除以相同元素的排列数。这正是多重集排列的公式：
   $$\text{Number of matrices} = \frac{k!}{c_{v_1}! c_{v_2}! \dots c_{v_p}!} = \frac{k!}{\prod_{v} c_v!}$$
   其中 $v$ 遍历多重集 $M$ 中所有不同的元素值。

3. 枚举维度 $(n, m)$:
   维度 $n$ 和 $m$ 必须是输入序列 $a_1, \dots, a_L$ 中的两个数。
   一个朴素的想法是遍历输入序列中所有可能的数对 $(a_i, a_j)$ 作为候选的 $(n, m)$。但这会导致 $O(L^2)$ 的复杂度，太慢。
   更好的方法是先统计输入序列中每个不同数值的出现次数。我们可以使用 std::map<int, int> cnt 来存储，cnt[x] 表示数值 $x$ 在输入中出现的次数。同时，将所有不同的数值存储在一个 std::vector<int> vals 中。

4. 优化枚举:
   我们不需要检查所有数对。对于一个可能的维度 $n=a$，我们只需要检查是否存在一个维度 $m=b$ 使得 $n \times m = k = L - 2$。这意味着 $b$ 必须等于 $k / a$，并且 $k$ 必须能被 $a$ 整除。
   所以，我们可以只遍历 vals 中的每一个数 $a$ 作为候选的 $n$：

   • 计算 $b = k / a$。
   • 检查 $a \times b$ 是否严格等于 $k$ (即 $k \% a == 0$)。
   • 检查 $a$ 和 $b$ 是否都是正整数 (题目保证输入是正整数，如果 $k/a$ 得到 0 或负数则无效，但由于 $k=L-2 \ge 1$ 且 $a \ge 1$，所以 $b=k/a \ge 1$)。
   • 最关键的一步：检查我们是否真的可以从输入的多重集中取出 $a$ 和 $b$ 作为维度。
     • Case 1: $a = b$: 我们需要从输入中取出两个 $a$。这要求 $a$ 在输入中至少出现了两次，即 cnt[a] >= 2。
     • Case 2: $a \neq b$: 我们需要从输入中取出一个 $a$ 和一个 $b$。这要求 $a$ 至少出现一次 (cnt[a] >= 1) 并且 $b$ 存在于输入中且至少出现一次 (cnt.count(b) 为真且 cnt[b] >= 1)。

5. 计算贡献:
   如果一对 $(a, b)$ (作为维度 $n, m$) 是有效的并且可以从输入中取出，我们需要计算对应的矩阵排列数并累加到总答案 ans 中。
   设 $S_{total}$ 是原始输入的多重集，其元素计数为 cnt。
   设 $M$ 是移除 $a$ 和 $b$ 后剩余的 $k$ 个元素的多重集，其元素计数为 $cnt’$。
   我们需要计算 $P(M) = \frac{k!}{\prod_{v} cnt’[v]!}$。
   直接计算 $cnt’$ 再算阶乘比较麻烦。我们可以利用 $cnt$ 和 $cnt’$ 的关系来简化：
   $$\prod_{v} cnt[v]! = \left( \prod_{v \in M} cnt’[v]! \right) \times \text{Factorials corresponding to removed } a, b$$
   令 $D_{total} = \prod_{v} cnt[v]!$ 和 $D_M = \prod_{v \in M} cnt’[v]!$。

   • Case 1: $a = b$: 我们移除了两个 $a$。所以 $cnt’[a] = cnt[a] - 2$，$cnt’[v] = cnt[v]$ for $v \neq a$。
     $D_{total} = D_M \times \frac{cnt[a]!}{(cnt[a]-2)!} = D_M \times cnt[a] \times (cnt[a]-1)$。
     因此 $D_M = \frac{D_{total}}{cnt[a] \times (cnt[a]-1)}$。
     $P(M) = \frac{k!}{D_M} = \frac{k! \times cnt[a] \times (cnt[a]-1)}{D_{total}}$。
   • Case 2: $a \neq b$: 我们移除了一个 $a$ 和一个 $b$。所以 $cnt’[a] = cnt[a] - 1$，$cnt’[b] = cnt[b] - 1$，$cnt’[v] = cnt[v]$ for $v \notin \{a, b\}$。
     $D_{total} = D_M \times \frac{cnt[a]!}{(cnt[a]-1)!} \times \frac{cnt[b]!}{(cnt[b]-1)!} = D_M \times cnt[a] \times cnt[b]$。
     因此 $D_M = \frac{D_{total}}{cnt[a] \times cnt[b]}$。
     $P(M) = \frac{k!}{D_M} = \frac{k! \times cnt[a] \times cnt[b]}{D_{total}}$。

6. 统一计算:
   我们可以先计算一个“基础”值：$Base = \frac{k!}{D_{total}} = k! \times \prod_{v} (cnt[v]!)^{-1} \pmod P$。
   这可以通过预计算阶乘和阶乘的模逆元来完成。

   • 预计算 fac[i] 和 invfac[i]。
   • 计算 inv_D_term = 1。遍历 cnt 中的每个 count，inv_D_term = (inv_D_term * comb.invfac(count)) % P。
   • 计算 base = (comb.fac(k) * inv_D_term) % P。
     然后，对于每个有效的维度对 $(a, b)$：
   • Case 1: $a = b$: (需要 cnt[a] >= 2)
     贡献 = (base * cnt[a] * (cnt[a] - 1)) % P。
   • Case 2: $a \neq b$: (需要 cnt[a] >= 1 且 cnt.count(b) 且 cnt[b] >= 1)
     贡献 = (base * cnt[a] * cnt[b]) % P。
     将所有情况的贡献累加到 ans 中。

7. 算法流程总结:

   1. 读入 $L$ 和 $L$ 个数。
   2. 统计每个正整数的出现次数 cnt，并将不同的正整数存入 vals。
   3. 计算 $k = L - 2$。如果 $k \le 0$，输出 0。
   4. 预计算阶乘 fac 和逆阶乘 invfac，最大到 $\max(k, \max(\text{counts in } cnt))$。
   5. 计算 $InvDenom = \prod_{v} (cnt[v]!)^{-1} \pmod P$。
   6. 计算 $Base = (k! \times InvDenom) \pmod P$。
   7. 初始化 ans = 0。
   8. 遍历 vals 中的每个数 $a$：
      a. 如果 $k$ 不能被 $a$ 整除，跳过。
      b. 计算 $b = k / a$。
      c. 如果 $a == b$:
      i. 如果 cnt[a] >= 2：
      term = (Base \times cnt[a] \times (cnt[a] - 1)) \pmod P
ans = (ans + term) \pmod P
      d. 如果 $a != b$:
      i. 如果 cnt.count(b) (即 $b$ 在输入中出现过) 并且 cnt[a] >= 1 并且 cnt[b] >= 1：
      term = (Base \times cnt[a] \times cnt[b]) \pmod P
ans = (ans + term) \pmod P
   9. 输出 ans。

时间复杂度

• 读入和计数：$O(L)$ 或 $O(L \log L)$，取决于计数方式。
• 预计算组合数：$O(\max(k, \max\_cnt)) = O(L)$。
• 计算 Base：$O(D)$，其中 D 是不同值的数量 ($D \le L$)。
• 主循环：遍历 D 个不同的值 a。内部进行除法、取模、查找 map（$O(\log D)$ 或 $O(1)$ 平均）和常数时间计算。总共 $O(D \log D)$ 或 $O(D)$。
• 整体复杂度约为 $O(L + D \log D)$ 或 $O(L \log L)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

// ... [省略了 ModInt, Barrett, Comb 等模板代码] ...
// 这些模板提供了模运算、组合数计算等基础功能
constexpr int P = 1000000007; // 定义模数
using Z = ModInt<P>; // 使用 ModInt 模板，定义类型别名 Z

// Comb 结构体用于计算组合数 (阶乘和逆阶乘)
struct Comb {
    int n;
    std::vector<Z> _fac;    // 阶乘
    std::vector<Z> _invfac; // 阶乘的逆元
    std::vector<Z> _inv;    // 逆元 (代码中未使用)

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }

    // 初始化组合数计算所需的表，直到 m
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1); // 即使不用，也需要调整大小

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i; // 计算阶乘
        }
        _invfac[m] = _fac[m].inv(); // 计算最大阶乘的逆元
        for (int i = m; i > n; i--) { // 反向计算阶乘逆元
            _invfac[i - 1] = _invfac[i] * i;
            // _inv[i] = _invfac[i] * _fac[i - 1]; // 计算逆元 (如果需要)
        }
        n = m;
    }

    // 返回 m! mod P
    Z fac(int m) {
        if (m > n) init(2 * m); // 动态扩展
        return _fac[m];
    }
    // 返回 (m!)^(-1) mod P
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    // Z inv(int m) { ... } // 返回 m^(-1) mod P (如果需要)

    // Z binom(int n, int m) { ... } // 计算 C(n, m) (本题未使用)

} comb; // 全局组合数对象

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 这里的 n 是输入的总数量 L = n*m + 2
    cin >> n;

    // 如果总数少于 3，无法选出 n, m 和至少一个元素，答案为 0
    if (n < 3) {
        cout << 0 << "\n";
        return 0;
    }

    map<int, int> cnt; // cnt[x] 存储数字 x 出现的次数
    vector<int> vals; // 存储出现过的不同的正整数
    int max_cnt = 0; // 记录出现次数的最大值，用于初始化 Comb

    // 读取 L 个数并统计频率
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x <= 0) continue; // 忽略非正整数 (题目保证是正整数，防御性编程)
        if (!cnt.count(x)) { // 如果是第一次遇到 x
            vals.push_back(x); // 加入不同值的列表
        }
        max_cnt = max(max_cnt, ++cnt[x]); // 更新频率和最大频率
    }

    int k = n - 2; // 矩阵元素的数量
    // 初始化组合数计算，需要计算到 max(k, max_cnt) 的阶乘
    comb.init(max(k, max_cnt));

    // 计算基础项中的分母的逆元部分: Product[ (cnt[x]!)^(-1) ]
    Z base_inv_denom = 1;
    for (int x : vals) { // 遍历所有不同的值 x
        base_inv_denom *= comb.invfac(cnt[x]); // 累乘 cnt[x]! 的逆元
    }

    // 计算基础项 Base = k! * Product[ (cnt[x]!)^(-1) ]
    Z base = comb.fac(k) * base_inv_denom;

    Z ans = 0; // 初始化总答案

    // 遍历所有不同的值 a 作为候选的维度 n
    for (int a : vals) {
        // 检查 a 是否能整除 k
        if (a <= 0 || k % a) continue; // a 必须是正数且是 k 的因子
        int b = k / a; // 计算对应的维度 m
        if (b <= 0) continue; // b 也必须是正数 (理论上 k>=1, a>=1 时 b>=1)

        // Case 1: a == b (n == m)
        if (a == b) {
            // 检查是否能取出两个 a 作为维度
            if (cnt[a] >= 2) {
                // 计算贡献： Base * cnt[a] * (cnt[a] - 1)
                Z cur = base; // 从基础项开始
                cur *= Z(cnt[a]) * (cnt[a] - 1); // 乘以对应的调整因子
                ans += cur; // 累加到答案
            }
        } 
        // Case 2: a != b (n != m)
        else {
            // 检查是否能取出一个 a 和一个 b 作为维度
            // 需要确保 b 存在于输入中 (cnt.count(b)) 且数量足够
            if (cnt.count(b) && cnt[a] >= 1 && cnt[b] >= 1) {
                 // 计算贡献： Base * cnt[a] * cnt[b]
                Z cur = base; // 从基础项开始
                cur *= Z(cnt[a]) * cnt[b]; // 乘以对应的调整因子
                ans += cur; // 累加到答案
            }
        }
    }

    // 输出最终答案 (已自动取模)
    cout << ans << "\n";

    return 0;
}