P1400 塔

題目描述

有N(2<=N<=600000)塊磚，要搭一個N層的塔，要求：如果磚A在磚B上面，那麼A不能比B的長度+D要長。問有幾種方法,輸出 答案 mod 1000000009的值.

輸入輸出格式

第一行： N，D 第二行： N個數，表示每塊磚的長度。

方案數，輸出要mod 1000000009

輸入輸出樣例

4 1
1 2 3 100

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 }