我叫王大錘,是一名特工。我剛剛接到任務(wù):在字節(jié)跳動(dòng)大街進(jìn)行埋伏,抓捕恐怖分子孔連順。和我一起行動(dòng)的還有另外兩名特工,我提議 1. 我們?cè)谧止?jié)跳動(dòng)大街的 N 個(gè)建筑中選定 3 個(gè)埋伏地點(diǎn)。 2. 為了相互照應(yīng),我們決定相距最遠(yuǎn)的兩名特工間的距離不超過(guò) D 。 我特喵是個(gè)天才! 經(jīng)過(guò)精密的計(jì)算,我們從X種可行的埋伏方案中選擇了一種。這個(gè)方案萬(wàn)無(wú)一失,顫抖吧,孔連順! …… 萬(wàn)萬(wàn)沒(méi)想到,計(jì)劃還是失敗了,孔連順化妝成小龍女,混在cosplay的隊(duì)伍中逃出了字節(jié)跳動(dòng)大街。只怪他的偽裝太成功了,就是楊過(guò)本人來(lái)了也發(fā)現(xiàn)不了的! 請(qǐng)聽(tīng)題:給定 N(可選作為埋伏點(diǎn)的建筑物數(shù))、 D(相距最遠(yuǎn)的兩名特工間的距離的最大值)以及可選建筑的坐標(biāo),計(jì)算在這次行動(dòng)中,大錘的小隊(duì)有多少種埋伏選擇。 注意: 1. 兩個(gè)特工不能埋伏在同一地點(diǎn) 2. 三個(gè)特工是等價(jià)的:即同樣的位置組合( A , B , C ) 只算一種埋伏方法,不能因“特工之間互換位置”而重復(fù)使用 數(shù)據(jù)范圍:
輸入描述:
第一行包含空格分隔的兩個(gè)數(shù)字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)第二行包含N個(gè)建筑物的的位置,每個(gè)位置用一個(gè)整數(shù)(取值區(qū)間為[0, 1000000])表示,從小到大排列(將字節(jié)跳動(dòng)大街看做一條數(shù)軸)
輸出描述:
一個(gè)數(shù)字,表示不同埋伏方案的數(shù)量。結(jié)果可能溢出,請(qǐng)對(duì) 99997867 取模
示例1
說(shuō)明
可選方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
加載中...