F. Expected Median - 题解

比赛与标签

比赛: Codeforces Round 964 (Div. 4) 标签: combinatorics, math 难度: *1500

题目大意喵~

主人你好呀！这道题是这样的：我们有一个只包含0和1的二进制数组 a，它的长度是 n。

我们的任务是，找出这个数组 a 中所有长度为 k 的子序列（注意 k 是一个奇数哦！）。对于每一个这样的子序列，我们都要找到它的中位数。

最后，把所有这些子序列的中位数全部加起来，得到一个总和。因为这个总和可能会很大很大，所以我们需要输出它对 10^9 + 7 取模之后的结果。

简单来说就是：求所有长度为 k 的子序列的中位数之和，喵~

解题思路来啦！

一看到要找“所有”子序列，直接暴力枚举肯定是不行的啦，组合数那么大，会累坏的！我们得想个聪明的办法才行，喵~

关键的第一步：中位数是什么？

题目告诉我们数组里只有0和1。那么，任何一个子序列也肯定只包含0和1。当我们对一个只含0和1的数组排序时，所有的0都会跑到前面，所有的1都会跑到后面，对吧？

比如一个子序列 [1, 0, 1, 0, 1]，排序后就是 [0, 0, 1, 1, 1]。

因为子序列的长度 k 是奇数，所以它的中位数就是排序后第 m = (k+1)/2 个位置的那个数。

那么问题来了，这个中位数什么时候会是 1 呢？ 只有当子序列里 1 的数量足够多，多到能占据第 m 个位置时，中位数才是 1。也就是说，子序列中 1 的数量必须大于 0 的数量。因为 k 是奇数，所以这就等价于 1 的数量至少要有 m = (k+1)/2 个！

• 如果 1 的数量 >= m，那么排序后第 m 个位置一定是 1，中位数就是 1。
• 如果 1 的数量 < m，那么排序后第 m 个位置一定是 0，中位数就是 0。

第二步：把问题变个身！

题目要求我们计算所有中位数的和。既然中位数只可能是 0 或者 1，那么：

总和 = (中位数为 1 的子序列数量) * 1 + (中位数为 0 的子序列数量) * 0

哇！这不就等于中位数为 1 的子序列的数量嘛！

所以，我们的问题就从“求和”变成了“计数”！只要数出来有多少个长度为 k 的子序列，它们的中位数是 1，就得到答案啦，是不是很神奇的说？

第三步：开始数数啦！

我们的新目标是：统计有多少个长度为 k 的子序列，其中 1 的数量至少为 m = (k+1)/2。

我们可以这样做：

1. 先遍历一遍原数组，数出里面总共有多少个 1（记作 ones）和多少个 0（记作 zeros）。
2. 一个长度为 k 的子序列，是由 i 个 1 和 k-i 个 0 组成的。
3. 我们希望中位数为 1，也就是说 1 的数量 i 必须满足 i >= m。同时，i 不能超过总长度 k。所以 i 的取值范围是 [m, k]。
4. 对于每一个满足条件的 i，我们来计算能构成多少个这样的子序列：
   • 从总共 ones 个 1 中选出 i 个，方法数是组合数 C(ones, i)。
   • 从总共 zeros 个 0 中选出 k-i 个，方法数是组合数 C(zeros, k-i)。
   • 根据乘法原理，形成一个包含 i 个 1 和 k-i 个 0 的子序列，总方法数就是 C(ones, i) * C(zeros, k-i)。
5. 最后，我们把所有 i 从 m 到 k 的情况的方案数全部加起来，就是最终的答案了！

最终公式： 答案 = Σ (从 i=m 到 k) [ C(ones, i) * C(zeros, k-i) ] (mod 10^9 + 7)

为了快速计算组合数 C(n, r)，我们需要预处理阶乘和阶乘的逆元，这是组合数学题目的常用技巧哦~

代码实现喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用 long long 来进行模运算，防止溢出喵
using ll = long long;

// 全局常量和预处理的数组
const int MOD = 1e9 + 7;
const int MAXN = 200005;
std::vector<ll> fact(MAXN);
std::vector<ll> invFact(MAXN);

// 快速幂，用来计算 (base^exp) % MOD
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 使用费马小定理求模逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和阶乘的逆元，这样后面算组合数就快啦
void precompute_factorials() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
}

// 计算组合数 C(n, r) mod p
ll nCr_mod_p(int n, int r) {
    // 如果 r < 0 或者 r > n，组合无意义，返回0
    if (r < 0 || r > n) {
        return 0;
    }
    // C(n,r) = n! / (r! * (n-r)!)
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

void solve() {
    int n, k;
    std::cin >> n >> k;
    int ones = 0;
    // 先数一数原数组里有多少个1
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        if (val == 1) {
            ones++;
        }
    }
    int zeros = n - ones;

    // 中位数为1的条件是：子序列中1的数量要大于0的数量。
    // 因为k是奇数，这等价于1的数量至少是 m = (k+1)/2。
    // 题目问的是中位数的和，因为中位数非0即1，所以这等价于统计中位数为1的子序列个数。
    
    // 一个子序列由 i 个 1 和 k-i 个 0 组成。
    // 从 `ones` 个1中选 i 个的方法数是 C(ones, i)。
    // 从 `zeros` 个0中选 k-i 个的方法数是 C(zeros, k-i)。
    // 总方法数是 C(ones, i) * C(zeros, k-i)。
    // 我们需要对所有满足条件的 i (即 i >= m) 进行求和。
    
    int m = (k + 1) / 2;
    ll total_sum = 0;

    // 遍历所有可能的1的数量 i (从 m 到 k)
    for (int i = m; i <= k; ++i) {
        // i = 子序列中1的数量
        // k-i = 子序列中0的数量
        
        // nCr_mod_p 会自动处理 i > ones 或 k-i > zeros 的情况，返回0
        // 因为 C(n,r) 在 r>n 或 r<0 时为0
        ll ways = (nCr_mod_p(ones, i) * nCr_mod_p(zeros, k - i)) % MOD;
        total_sum = (total_sum + ways) % MOD;
    }

    std::cout << total_sum << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快一点！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在处理所有测试用例之前，先做一次预处理
    precompute_factorials();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: O(MAXN + T * k) 的说。

  • precompute_factorials() 函数需要 O(MAXN) 的时间来预处理阶乘和逆元，其中 MAXN 是 n 的最大可能值。这个操作只需要执行一次。
  • 对于每个测试用例 T，solve() 函数中的循环会从 m 到 k，最多执行 k 次。每次循环内部的计算都是 O(1) 的（因为我们已经预处理了！）。所以每个测试用例的时间是 O(k)。
  • 总时间就是预处理加上所有测试用例的时间，即 O(MAXN + T * k)。

• 空间复杂度: O(MAXN) 的说。

  • 我们需要两个大小为 MAXN 的数组 fact 和 invFact 来存储阶乘和它们的逆元。所以空间开销是线性的。

小猫娘的知识宝库

这道题真有趣，融合了观察和组合数学，喵~ 让我们总结一下学到了什么吧！

1. 问题转化思想: 这是解题最最核心的一步！把一个看起来很复杂的“求和”问题（求中位数之和），通过分析题目性质（二进制数组、奇数长度），转化成了一个更简单的“计数”问题（统计中位数为1的子序列数量）。这种思维转变在算法竞赛中非常重要哦！

2. 组合数学应用: 一旦问题变成了计数，我们就要想到用组合数学的工具。这里我们用到了组合数 C(n, r) 来计算“从 n 个物品中选 r 个”的方案数，并用乘法原理将选择 1 和选择 0 的方案数组合起来。

3. 预处理技巧: 对于需要反复计算组合数的题目，先花 O(N) 的时间预处理阶乘和逆元，之后每次查询组合数就能做到 O(1)，这是一个非常经典且高效的优化手段。

4. 模运算: 只要看到“结果可能很大，请对...取模”的字样，就要时刻记得在每一步乘法和加法后都进行取模操作，防止中间结果溢出 long long 的范围，喵~

希望这篇题解能帮助到你呐！继续加油，享受解题的乐趣吧！喵~ >w<