北京师范大学第十七届程序设计竞赛决赛-重现赛 - D

北京师范大学第十七届程序设计竞赛决赛-重现赛 - D - 选数字（概率期望）

本文主要是介绍北京师范大学第十七届程序设计竞赛决赛-重现赛 - D - 选数字（概率期望），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://ac.nowcoder.com/acm/contest/895/D

思路：样例的解释：

选中1，从右边四个数中选择一个数，共有4种选法，其概率是 $C_4^1/C_5^2 $
选中2，从右边三个数中选择一个数，共有3种选法，其概率是 $C_3^1/C_5^2 $
选中3，从右边两个数中选择一个数，共有2种选法，其概率是 $C_2^1/C_5^2 $
选中4，从右边一个数中选择一个数，共有1中选法，其概率是 $C_1^1/C_5^2 $
期望 $E$ 为 $1*C_4^1/C_5^2+2*C_3^1/C_5^2+3*C_2^1/C_5^2+4*C_1^1/C_5^2$ 。
答案为 $E*C_5^2$ 等于 $1*C_4^1+2*C_3^1+3*C_2^1+4*C_1^1$ 。

所以这题的解法就是，先从小到大排序，从第一个数开始遍历，将被遍历到的数作为最小的数，再从其右边的数中选择 $k-1$ 个数，使其构成 $k$ 个数，最后答案就是 $\sum _{i=1}^{n}a[i]*C_{n-i}^{k-1}$ 。

/****   █████▒█    ██  ▄████▄   ██ ▄█▀       ██████╗ ██╗   ██╗ ██████╗* ▓██   ▒ ██  ▓██▒▒██▀ ▀█   ██▄█▒        ██╔══██╗██║   ██║██╔════╝* ▒████ ░▓██  ▒██░▒▓█    ▄ ▓███▄░        ██████╔╝██║   ██║██║  ███╗* ░▓█▒  ░▓▓█  ░██░▒▓▓▄ ▄██▒▓██ █▄        ██╔══██╗██║   ██║██║   ██║* ░▒█░   ▒▒█████▓ ▒ ▓███▀ ░▒██▒ █▄       ██████╔╝╚██████╔╝╚██████╔╝*  ▒ ░   ░▒▓▒ ▒ ▒ ░ ░▒ ▒  ░▒ ▒▒ ▓▒       ╚═════╝  ╚═════╝  ╚═════╝*  ░     ░░▒░ ░ ░   ░  ▒   ░ ░▒ ▒░*  ░ ░    ░░░ ░ ░ ░        ░ ░░ ░*           ░     ░ ░      ░  ░**/
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
const int maxn = 2e5 + 7;
const int mod = 1000000007;
typedef long long ll;
int a[maxn];
ll fac[maxn];
void table()
{fac[0] = 1;for(ll i = 1; i <= 100005; i++)fac[i] = (i % mod * fac[i-1] % mod) % mod;
}
ll qpow(ll a, ll b)
{ll ans = 1;a %= mod;while(b){if(b & 1) ans = a * ans % mod;a = a * a % mod;b >>= 1;}return ans;
}
ll inv(ll x)
{return qpow(x, mod - 2);
}
ll C(ll n, ll k)
{return (fac[n] * inv(fac[k] * fac[n - k])) % mod;
}
int main()
{table();int T, n, k; scanf("%d", &T);while(T--){scanf("%d%d",&n, &k);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);sort(a + 1, a + 1 + n);ll ans = 0;for(int i = 1; i <= n; i++){ans += a[i] * C(n - i, k - 1);ans %= mod;}cout << ans << endl;}
}

这篇关于北京师范大学第十七届程序设计竞赛决赛-重现赛 - D - 选数字（概率期望）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！