P6522 [CEOI 2010] tower (day2)题目背景古巴比伦人决定建造一座塔。题目描述这座塔共有n nn层每层由一个边长为a i a_iai​的立方体石块构成。一个石块i ii能够直接放在石块j jj上当且仅当a i ≤ a j D a_i \leq a_jDai​≤aj​D其中D DD为一个给定的常数。你需要求出如果使用全部的石块有多少种不同的搭建方案。输出答案m o d 10 9 9 \bmod\ 10^99mod1099的结果。注意即使两个石块的边长相同也看做不同的石块。输入格式输入第一行两个整数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^99mod1099的结果。输入输出样例 #1输入 #14 1 1 2 3 100输出 #14输入输出样例 #2输入 #26 9 10 20 20 10 10 20输出 #236说明/提示【样例解释】样例 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实现#includecstdio#includealgorithm#definelllonglongusingnamespacestd;intarr[620005];constintMOD1e99;intmain(){intn,k;ll Ans1;scanf(%d %d,n,k);for(inti1;in;i)scanf(%d,arr[i]);sort(arr1,arr1n);for(intl1,r1;rn;r){while(arr[l]karr[r])l;AnsAns*(r-l1)%MOD;}printf(%lld,Ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容