运用逆元优化组合计算#数论

 数论基础知识和模板-CSDN博客

问题分析

题目要求统计满足特定条件的排列数目。关键在于：

1. 从给定的数组中选择两个数作为 n 和 m
2. 剩余的数必须能够组成 n 个 m 或 m 个 n 的结构
3. 计算所有可能的有效排列数目

完整

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9+7;

// 快速幂计算 a^b % MOD
LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int sum; cin >> sum;               // 输入数组长度
    int scale = sum - 2;              // 目标排列长度 = sum - 2
    
    // 预处理阶乘数组 jc[i] = i! % MOD
    vector<LL> jc(500001, 1), invjc(500001);
    for (int i = 1; i <= 500000; i++) jc[i] = jc[i-1] * i % MOD;
    
    // 预处理阶乘的逆元数组 invjc[i] = (i!)^(-1) % MOD
    for (int i = 0; i <= 500000; i++) invjc[i] = qpow(jc[i], MOD-2);
    
    // 统计每个数的出现次数
    vector<int> bucket(500001);
    for (int i = 0; i < sum; i++) {
        int x; cin >> x;
        bucket[x]++;
    }
    
    LL ans = 0;
    // 枚举所有可能的因子对 (i, scale/i)
    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]--;  // 临时减少计数
            
            // 计算剩余元素的排列数目
            LL 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;
}

核心算法解析

1. 数学原理

• 排列数计算：对于长度为 scale 的排列，若元素 x 出现 c_x 次，则排列数为：

  scale! / (c_1! * c_2! * ... * c_k!)
  

   

  在模运算下，除法转换为乘以逆元：a/b ≡ a * b^(-1) (mod MOD)

• 逆元计算：使用费马小定理 a^(MOD-1) ≡ 1 (mod MOD)，因此 a^(-1) ≡ a^(MOD-2) (mod MOD)

2. 预处理优化

• 阶乘数组：jc[i] 存储 i! % MOD，递推公式：jc[i] = jc[i-1] * i % MOD
• 逆元数组：invjc[i] 存储 (i!)^(-1) % MOD，通过快速幂计算：invjc[i] = qpow(jc[i], MOD-2)

3. 因子枚举策略

• 枚举范围：遍历 i 从 1 到 scale，检查 i 是否是 scale 的因子
• 条件判断：若 scale % i == 0 且数组中存在足够的 i 和 scale/i，则它们可能是有效解
• 排列计算：临时减少 i 和 scale/i 的计数，计算剩余元素的排列数并累加

4. 复杂度分析

• 预处理：阶乘和逆元计算均为 O (N)
• 枚举因子：O (scale)，实际有效因子对数量远小于 scale
• 排列计算：每次 O (N)，但仅在有效因子对时执行
• 总复杂度：O (N + scale)，其中 N = 5e5