有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
乘法原理
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define lli long long int
6 #include<algorithm>
7 using namespace std;
8 const int MAXN=600001;
9 const int mod=1000000009;
10 int read(int & n)
11 {
12 char c='.';int x=0,flag=0;
13 while(c<'0'||c>'9')
14 {c=getchar(); if(c=='-')flag=1; }
15 while(c>='0'&&c<='9')
16 {x=x*10+(c-48);c=getchar();}
17 if(flag==1)n=-x;else n=x;
18 }
19 int n,d;
20 int a[MAXN];
21 lli ans=1;
22 int top=1;
23 int maxn=1;
24 int main()
25 {
26 read(n);read(d);
27 for(int i=1;i<=n;i++)
28 read(a[i]);
29 sort(a+1,a+n+1);
30 for(int i=2;i<=n;i++)
31 {
32 while(a[i]>a[top]+d)
33 {
34 top++;
35 }
36 ans=ans*(i-top+1);
37 ans=ans%mod;
38 }
39 //printf("%d",ans);
40 cout<<ans;
41 return 0;
42 }