Gym 100952 D. Time to go back
1 second
256 megabytes
standard input
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,显然是一个排列组合,但数据量大,构造组合函数精度容易出问题,因此可以用杨辉三角
vis[i][j]=vis[i-1][j-1]+vis[i-1][j];
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll vis[][],val[],n,m,k,d,t;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
mem(vis);
for(int i=;i<;i++)
{
vis[i][]=;
for(int j=;j<=i;j++)
{
vis[i][j]=(((vis[i-][j-])%MOD)+((vis[i-][j])%MOD))%MOD;
}
}
scanf("%lld",&t);
while(t--)
{
ll ans=,pos=;
scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
for(ll i=;i<n;i++)
scanf("%lld",&val[i]);
sort(val,val+n,cmp);
for(ll i=;i<n;i++)
{
if(val[i]>=d) ans++;
else break;
}
if(n-ans==) pos=vis[ans][m];
else if(ans<k || n<m) pos=;
else
{
for(ll i=k;i<=ans;i++)
{
if(m-i<) break;
pos=(pos+(vis[ans][i]*vis[n-ans][m-i])%MOD)%MOD;
}
}
printf("%lld\n",pos);
}
}
最新文章
- 超千个节点OpenStack私有云案例(1):CERN 5000+ 计算节点私有云
- ASP.NET WebAPI 12 Action的执行
- Spring整合Shiro做权限控制模块详细案例分析
- A51汇编器的解释
- workflow--相关笔记
- 关于ViewPager+Fragment中的坑
- 第一册:lesson 101。
- jquery cookie问题
- makefile笔记6 - makefile条件判断
- C#获取中国天气网免费天气预报信息
- 【css】垂直居中的几种写法
- DeviceIoControl函数对应的四种数据交换方式
- BZOJ3500 : PA2008 Cliquers
- python安装pip和使用pip安装Python库类比如pip安装beautifulsoup4
- 10013: 以一种访问权限不允许的方式做了一个访问套接字的尝试【WCF异常】
- python学习,day3:函数式编程,带参数
- 「Neerc2016」Expect to Wait
- 吉哥系列故事――完美队形II HDU - 4513(马拉车变一下形)
- 教你使用 Reflexil 反编译.NET 转
- java 基础 --int 和Integer的区别