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


乘法原理
 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

    attack
  • 洛谷P4165 [SCOI2007]组队(排序 堆)

    \[A H_i + B S_i \leqslant C + AminH + BminS\]

    attack
  • 洛谷T21778 过年

    题目描述 有 n(1 \leq n \leq 10^5)n(1≤n≤105) 个小朋友,过年了,要发放 m(1 \leq m \leq 10^5)m(1≤m≤1...

    attack
  • Codeforces Round #186 (Div. 2)A、B、C、D、E

    Ilya得到了一个礼物,可以在删掉银行账户最后和倒数第二位的数字(账户有可能是负的),也可以不做任何处理。

    xindoo
  • 洛谷T21778 过年

    题目描述 有 n(1 \leq n \leq 10^5)n(1≤n≤105) 个小朋友,过年了,要发放 m(1 \leq m \leq 10^5)m(1≤m≤1...

    attack
  • 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

    Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

    ACM算法日常
  • 洛谷P4165 [SCOI2007]组队(排序 堆)

    \[A H_i + B S_i \leqslant C + AminH + BminS\]

    attack
  • loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

    attack
  • Leetcode 870. Advantage Shuffle

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • 洛谷P4781 【模板】拉格朗日插值(拉格朗日插值)

    \[f(x) = \sum_{i = 1}^n y_i \prod_{j \not = i} \frac{k - x[j]}{x[i] - x[j]}\]

    attack

扫码关注云+社区

领取腾讯云代金券