P1400 塔

有N(2<=N<=600000)块砖，要搭一个N层的塔，要求：如果砖A在砖B上面，那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值.

输入格式：

第一行： N，D 第二行： N个数，表示每块砖的长度。

输出格式：

方案数，输出要mod 1000000009

输入样例#1： 复制

4 1
1 2 3 100

输出样例#1： 复制

4
思路：数学
首先排序，这是大家能想到的第一思路。
其次计算 num[i]--num[i]+d中数的个数，ans每次乘这个数，乘法原理解决。

#include
#include
#include
#include
#define mod 1000000009
using namespace std;
int n,d;
int num[];
int l,r,mid,ll,rr;
long long ans=;
bool judge(int i){
if(num[mid]<=num[i]) return true;
else return false;
}
bool juddge(int i){
if(num[mid]<=num[i]+d) return true;
else return false;
}
int main(){
scanf("%d%d",&n,&d);
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
sort(num+,num++n);
for(int i=;i<=n;i++){
l=;r=n;
while(l<=r){
mid=(l+r)/;
if(judge(i)) l=mid+;
else r=mid-;
}
ll=;rr=n;
while(ll<=rr){
mid=(ll+rr)/;
if(juddge(i)) ll=mid+;
else rr=mid-;
}
ans=ans*(ll-l+)%mod;
}
cout<<ans;
}