小红的最大中位数

[编程题]小红的最大中位数

热度指数：331 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一个数组，她准备选择一个子序列，使得该子序列的中位数尽可能大。小红想知道，一共有多少种方案？
奇数长度的子序列中位数为中间的那个数，偶数长度的子序列中位数为中间两个数的平均数。

输入描述:

第一行输入一个正整数，代表数组大小、待选择的子序列长度。
第二行输入个正整数。代表小红拿到的数组。

输出描述:

一个整数，代表选择的方案数。由于答案可能过大，请对取模。

示例1

输入

3
1 2 2

输出

说明

最大中位数为 2。
选一个 2 有两种方案，选两个 2 有一种方案，选三个数有一种方案。

算法知识视频讲解

牛客126208132号

/* 选的最大值个数比其他数至少多一个即可 */
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, maxx;
unordered_map<int,int> mp;
ll fact[N], infact[N], L[N];

ll ksm(ll x, ll y) {
    ll res = 1;
    while( y ) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for(int i=1; i<=n; i++) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * ksm(i, mod - 2) % mod;
    }
}

ll C(int n, int m) {
    return ((fact[n] * infact[m] % mod) * infact[n - m]) % mod;
}

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    init();
    for(int i=1; i<=n; i++) {
        int t; cin >> t;
        maxx = max(maxx, t);
        mp[t] ++;
    }
    int right = mp[maxx], left = n - right;
    L[0] = 1;
    for(int i=1; i<=left; i++) {
        L[i] = (L[i - 1] + C(left, i)) % mod;
    }
    ll res = 0;
    for(int i=1; i<=right; i++) {
        (res += C(right, i) * L[i - 1]) %= mod;
    }
    cout << res;
    
    return 0;
}

发表于 2025-03-08 01:31:48 回复(0)

牛客745468920号

费马小定理模逆元

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;

// 快速幂求 a^b % mod
long long modPow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 计算 a 在 mod 意义下的逆元（模逆元）
long long modInverse(long long a, long long mod) {
    return modPow(a, mod - 2, mod);
}

// 计算组合数 C(n, k) 并对 MOD 取模
long long C(int n, int k) {
    if (k > n - k)
        k = n - k;  // 利用对称性 C(n, k) = C(n, n-k)

    long long result = 1;
    for (int i = 0; i < k; i++) {
        // 计算分子部分：(n-i)
        result = result * (n - i) % MOD;
        // 乘以 (i+1) 的模逆元，相当于除以 (i+1)
        result = result * modInverse(i + 1, MOD) % MOD;
    }
    return result;
}


int main() {
    int len;
    cin >> len;
    vector<int>nums(len);
    for (int i = 0; i < len; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    int mid_num = nums[len - 1];
    int index = lower_bound(nums.begin(), nums.end(), mid_num) - nums.begin();
    if (index == len - 1) {
        cout << 1 << endl;
    } else {
        int mod = 1e9 + 7;
        long long res = 0;
        for (int i = 0; i <= index; i++) {
            for (int j = i + 1; j <= len - index; j++) {
                res += C(len - index, j) * C(index, i);
                res %= mod;
            }
        }
        cout << res << endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-03-12 16:59:17 回复(0)