hihocoder 1546

#1546 : 集合计数

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个包含N个整数的集合S={A1, A2, ... AN}，以及一个给定的整数K，请计算有多少个S的子集满足其中的最大值与最小值的和小于等于K。

例如对于S={4, 2, 5, 8}以及K=7,满足的条件的子集有以下4个:{2}, {2, 4}, {2, 5}, {2, 4, 5}。

输入

第一行包含两个整数N和K。

第二行包含N个整数A1, A2, ... AN。

对于30%的数据，1 <= N <= 20

对于70%的数据，1 <= N <= 1000

对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 1000000000, 0 <= K <= 2000000000, A1 ~ AN 两两不同。

输出

输出满足条件的子集数目。由于答案可能非常大，你只需要输出答案除以1000000007的余数。

样例输入

4 7  
4 2 5 8

样例输出

4
思路：二分+前缀和

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e5+10;
 5 const ll mod=1e9+7;
 6 
 7 ll a[N];
 8 ll b[N];
 9 ll c[N];
10 
11 void init(){
12     b[1]=1;
13     ll x=2;
14     for(int i=2;i<=N;i++){
15         b[i]=(b[i-1]+x)%mod;
16         x=x*2%mod;
17     }
18     for(int i=1;i<=N;i++)
19         c[i]=(mod+c[i-1]+b[i])%mod;
20 }
21 int main(){
22     ll n,k;
23     init();
24     scanf("%lld%lld",&n,&k);
25     ll sum=0;
26     for(int i=1;i<=n;i++){
27         scanf("%lld",&a[i]);
28         if(2*a[i]<=k) sum++;
29     }
30     sort(a+1,a+1+n);
31 
32     for(int i=1;i<=n;i++){
33         ll x=k-a[i];
34         if(x>0){
35             int kk=lower_bound(a+1,a+1+n,x)-a;
36             if(a[kk]>x) kk--;
37             kk=min(kk,i-1);
38             int len=i-kk-1;
39             int r=len+(kk-1);
40             sum=(sum+kk+c[r]-c[len-1]+mod)%mod;
41            // cout<<a[i]<<" "<<sum<<endl;
42         }
43 
44     }
45     cout<<(sum+mod)%mod<<endl;
46 }