当前位置：首页 > news >正文

打卡信奥刷题（3039）用C++实现信奥题 P6522 [CEOI 2010] tower (day2)

news 2026/6/18 1:04:18

P6522 [CEOI 2010] tower (day2)

题目背景

古巴比伦人决定建造一座塔。

题目描述

这座塔共有n nn层，每层由一个边长为a i a_iai的立方体石块构成。一个石块i ii能够直接放在石块j jj上当且仅当a i ≤ a j + D a_i \leq a_j+Dai≤aj+D，其中D DD为一个给定的常数。

你需要求出如果使用全部的石块，有多少种不同的搭建方案。输出答案m o d 10 9 + 9 \bmod\ 10^9+9mod109+9的结果。

注意：即使两个石块的边长相同，也看做不同的石块。

输入格式

输入第一行两个整数n , D n,Dn,D。

第二行n nn个整数a 1 , … , a n a_1,\dots,a_na1,…,an，表示每个立方体石块的边长。

输出格式

输出一行一个整数，表示方案总数m o d 10 9 + 9 \bmod\ 10^9+9mod109+9的结果。

输入输出样例 #1

输入 #1

4 1 1 2 3 100

输出 #1

输入输出样例 #2

输入 #2

6 9 10 20 20 10 10 20

输出 #2

说明/提示

【样例解释】

样例 1 解释

首先把边长为100 100100的石块放在底部，其余的石块可以任意顺序放置，除了以下两种情况：2,1,31,3,2。

样例 2 解释

首先不允许在10 1010上面放20 2020。

所以就把20 2020一堆放在底下，10 1010一堆放在上面。

即( 3 ! ) × ( 3 ! ) = 36 (3!)\times (3!)=36(3!)×(3!)=36。

【数据规模与约定】

对于10 % 10\%10%的数据，保证n ≤ 10 n\le 10n≤10；
对于30 % 30\%30%的数据，保证方案数不超过10 6 10^6106；
对于45 % 45\%45%的数据，保证n ≤ 20 n\le 20n≤20；
对于70 % 70\%70%的数据，保证n ≤ 70 n\le 70n≤70；
对于100 % 100\%100%的数据，保证2 ≤ n ≤ 6.2 × 10 5 2\le n\le 6.2\times 10^52≤n≤6.2×105，输入中所有数字为不超过10 9 10^9109的正整数。

【说明】

题目译自 CEOI 2010 day 2T3 tower。

翻译版权为题目提供者 @ShineEternal 所有，未经许可禁止转载。

C++实现

#include<cstdio>#include<algorithm>#definelllonglongusingnamespacestd;intarr[620005];constintMOD=1e9+9;intmain(){intn,k;ll Ans=1;scanf("%d %d",&n,&k);for(inti=1;i<=n;i++)scanf("%d",&arr[i]);sort(arr+1,arr+1+n);for(intl=1,r=1;r<=n;r++){while(arr[l]+k<arr[r])l++;Ans=Ans*(r-l+1)%MOD;}printf("%lld",Ans);return0;}