考点：组合数学

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5，k ≤ 1e5
• 元素值域：a_i ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

1. 判断是分类计数（相加）还是分步计数（相乘）。
2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

• 把排列和组合搞混。
• 取模意义下直接做除法（应乘逆元）。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 5 2 / 2 5 3 4 20 → 输出 4

第一个方案，删除[3]。

第二个方案，删除[4]。

第三个方案，删除[3,4]。

第四个方案，删除[2]。