2017ecjtu-summer training #6 Gym 100952D
1 second
256 megabytes
standard output
You have been out of Syria for a long time, and you recently decided to come back. You remember that you have M friends there and since you are a generous man/woman you want to buy a gift for each of them, so you went to a gift store that have N gifts, each of them has a price.
You have a lot of money so you don't have a problem with the sum of gifts' prices that you'll buy, but you have K close friends among your M friends you want their gifts to be expensive so the price of each of them is at least D.
Now you are wondering, in how many different ways can you choose the gifts?
The input will start with a single integer T, the number of test cases. Each test case consists of two lines.
the first line will have four integers N, M, K, D (0 ≤ N, M ≤ 200, 0 ≤ K ≤ 50, 0 ≤ D ≤ 500).
The second line will have N positive integer number, the price of each gift.
The gift price is ≤ 500.
Print one line for each test case, the number of different ways to choose the gifts (there will be always one way at least to choose the gifts).
As the number of ways can be too large, print it modulo 1000000007.
2
5 3 2 100
150 30 100 70 10
10 5 3 50
100 50 150 10 25 40 55 300 5 10
3
126 题意 一共有n件礼物,m个朋友,k个好朋友,好朋友的礼物必须超过d 给出n个礼物的价格(都不相同),问选择方案有多少?
解析 组合数学 令价格大于等于d的数量为sum c[sum][k]*c[n-k][m-k], 显然是错误的,因为会有好多重复的组合,
比如 (100 150 300 50 55)和(100 55 50 150 300)是重复的。
所以 应该是分步 分类(price >= d 的与 < d 的分开算, 这样就不会相同的礼物选2次了)
首先 C[sum][k] * C[n - sum][m - k];
然后 C[sum][k + 1] * C[n - sum][ m - k - 1];
接着 C[sum][k + 2] * C[n - sum][ m - k - 2];
......
一直循环到 i<=m&&i<=sum (看代码)
AC代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#define maxn 210
#define mod 1000000007
using namespace std;
typedef long long ll;
ll c[maxn][maxn];
int a[maxn];
void yanghui() //杨辉三角求C几几;
{
memset(c,,sizeof(c));
int i,j;
for(i=;i<maxn;i++)
c[i][]=;
for(i=;i<maxn;i++)
{
for(j=;j<=i;j++)
{
c[i][j]=(c[i-][j-]+c[i-][j])%mod;
}
}
}
int main()
{
int t;
int i,j;
int n,m,k,d;
yanghui();
cin>>t;
while(t--)
{
cin>>n>>m>>k>>d;
int sum=;
ll ans=;
for(i=;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=;i<n;i++)
{
if(a[i]>=d)
{
sum++;
}
}
for(i=k;i<=m&&i<=sum;i++)
{
ans=(ans+c[sum][i]*c[n-sum][m-i])%mod;
}
cout<<ans<<endl;
}
}
最新文章
- 一条Sql语句分组排序并且限制显示的数据条数
- [转] How to change font settings for all UI elements (toolbar and context menus, property editors, etc.)
- Tomcat6性能优化
- 3. 使用绘图API自定义视图 --- 旋转的方块
- idea14使用maven创建web工程
- chmod,chown和chgrp的区别
- js获取url中的参数对象、js生成带参数的url
- Linux远程访问windows时,出现";连接被对端重置";错误
- 在cad中画一条长500mm,垂直90度的线段
- 使用ActionBar实现Tab导航(快速生成Tab样式)
- 挑战一下吧!C#测试开发工程师英语面试题
- 关于NIOS ii烧写的几种方式(转)
- .Net高级进阶,在复杂的业务逻辑下,如何以最简练的代码,最直观的编写事务代码?
- axios跨域
- jpa一对多映射案例
- RPA基础
- 自学Python4.3-装饰器固定格式
- 阿里云部署Web项目
- 【原创】运维基础之Docker(6)性能
- 【读书笔记】iOS-属性