运用逆元优化组合计算#数论
数论基础知识和模板-CSDN博客
问题分析
题目要求统计满足特定条件的排列数目。关键在于：
- 从给定的数组中选择两个数作为 n 和 m
- 剩余的数必须能够组成 n 个 m 或 m 个 n 的结构
- 计算所有可能的有效排列数目
完整
#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! % MODvector<LL> jc(500001, 1), invjc(500001);for (int i = 1; i <= 500000; i++) jc[i] = jc[i-1] * i % MOD;// 预处理阶乘的逆元数组 invjc[i] = (i!)^(-1) % MODfor (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