計數原理的簡單方法-tft每日頭條

計數原理的簡單方法

生活更新时间:2024-11-28 19:28:34

給定一個包含N個整數的集合S={A1, A2, ... AN}，以及一個給定的整數K，請計算有多少個S的子集滿足其中的最大值與最小值的和小于等于K。

例如對于S={4, 2, 5, 8}以及K=7,滿足的條件的子集有以下4個:{2}, {2, 4}, {2, 5}, {2, 4, 5}。

Input

第一行包含兩個整數N和K。

第二行包含N個整數A1, A2, ... AN。

對于30%的數據，1 <= N <= 20

對于70%的數據，1 <= N <= 1000

對于100%的數據，1 <= N <= 100000, 0 <= Ai <= 1000000000, 0 <= K <= 2000000000, A1 ~ AN 兩兩不同。

Output

輸出滿足條件的子集數目。由于答案可能非常大，你隻需要輸出答案除以1000000007的餘數。

Sample Input

Sample Output

題意：見題目描述

思路：這道題其實到現在我也沒能理解，但是有兩個結論先記下來：①：以第i個元素開頭，第j個元素結尾的集合的個數為2^(j-i-1)個(最大小值必定位于集合内，大小位于兩者之間的元素有j−i−1個，每個元素都有兩種可能性，出現/不出現)。②：以第i個元素開頭，第j以及所有x(i<x<j)結尾的集合共有2^（j-i）-1個。

舉例說明以上兩個結論: 集合 {1，2，3，4，5，6，7}

結論1：eg：i=2，j=5，集合有{2，5}、{2，3，5}、{2，4，5}、{2，3，4，5}共4個

結論2：eg：i=2，j=5，集合有{2，5}、{2，3，5}、{2，4，5}、{2，3，4，5}、{2，4}、{2，3，4}、{2，3}共7個

計數原理的簡單方法（集合計數HihoCoder-1546計數）1

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部

网友关注

生活連身褲怎麼挑選适合自己的
連身褲怎麼挑選适合自己的?蘋果型身材：硬挺材質、一字領，避免高腰收緊款式四肢纖細、身體中間肉比較多的蘋果身形，建議選擇硬挺材質的連身褲，這樣身形就不會因為貼身材質而被凸顯，反而能修飾線條，看起來更纖細、更拉長!此外，一字領的連身褲也是好的選... 2022-07-17
生活油表燈亮還能用多久
大家好，我是小李。現在的汽車其實并沒有所謂的副油箱，車子儀表盤上面的油表燈亮黃色燈就代表車輛快沒有油了，需要盡快加油否則的話可能會半路趴窩。但是這個油表燈亮起來的時候實際上油箱裡的汽油還是很可觀的，并不會像大家擔心的那樣已經見底了。隻不過油... 2022-10-31
生活用電餅铛做蛋黃溶豆的方法
用電餅铛做蛋黃溶豆的方法?用料：奶粉30克（蛋黃蛋清各用15g）、雞蛋2個、檸檬汁6滴、錫紙或油紙，下面我們就來說一說關于用電餅铛做蛋黃溶豆的方法?我們一起去了解并探讨一下這個問題吧!用電餅铛做蛋黃溶豆的方法用料：奶粉30克（蛋黃蛋清各用1... 2022-06-15
生活銀行卡不在身邊怎麼查卡号
銀行卡不在身邊怎麼查卡号?銀行網點櫃台查詢：用戶在櫃台提供個人身份證，工作人員會幫忙進行卡号查詢，今天小編就來聊一聊關于銀行卡不在身邊怎麼查卡号?接下來我們就一起去研究一下吧!銀行卡不在身邊怎麼查卡号銀行網點櫃台查詢：用戶在櫃台提供個人身份... 2022-06-08
生活如果迷路了怎麼辦一年級
如果迷路了怎麼辦一年級?小朋友們平時應當注意準确地記下自己家庭所在的地區、街道、門牌号碼、電話号碼及父母的工作單位名稱、地址、電話号碼等，以便需要聯系時能夠及時聯系，下面我們就來說一說關于如果迷路了怎麼辦一年級?我們一起去了解并探讨一下這個... 2022-06-05
生活無鉛焊錫線和有鉛焊錫線的區别
無鉛焊錫線和有鉛焊錫線的區别?有鉛錫線和無鉛錫線區别為：外觀特色有所不同、氧化程度略微不同、熔點不同、焊接不同，今天小編就來聊一聊關于無鉛焊錫線和有鉛焊錫線的區别?接下來我們就一起去研究一下吧!無鉛焊錫線和有鉛焊錫線的區别有鉛錫線和無鉛錫線... 2022-07-02
生活被出具審計保留意見的上市公司
年報披露落下帷幕，A股有41家上市公司審計意見類别為“無法表示意見”，41股具體特征如下：（1）市值維度：41股股市值均不足50億，僅6股市值超20億不足50億【ST銀河、*ST金洲、SST佳通、日海智能、深大通、科華生物】，16股市值不足... 2022-12-02
生活世界無窮願無盡海天寥廓立多時的意思
世界無窮願無盡海天寥廓立多時的意思?世界将會永無止盡地發展下去，我的願望也如無窮的宇宙一樣永無休止；面對寂寥廣闊的大海藍天，不覺為之怅然，伫立良久寥廓：是指寂寥、廣闊此詩作者梁啟超自好任公，以天下為己任，故寫這首詩以自我期勉，今天小編就來聊... 2022-07-01
生活怎樣鑒定枸杞的好壞
一些藥食同源的中藥總是被養生一族列為冬季養生的首選，比如說枸杞。枸杞味甘、性平，有滋補肝腎、益精明目的功效。現代研究證實，枸杞能夠保肝、降血糖、軟化血管，并且對癌細胞的生産和擴散有明顯的抑制作用。那麼，到底如何選擇枸杞呢？是黑枸杞好還是紅枸... 2022-11-13
生活玉米火腿包如何做
玉米火腿包如何做?把高筋面粉、雞蛋液、牛奶、細砂糖、食鹽、和幹酵母粉混合，揉至光滑，加入軟化的黃油揉至拉出薄膜狀，把面團滾圓放在室溫下進行基礎發酵，我來為大家講解一下關于玉米火腿包如何做?跟着小編一起來看一看吧!玉米火腿包如何做把高筋面粉、... 2022-06-07
生活激勵孩子成長的良言妙語
激勵孩子成長的良言妙語?孩子,你仍然很棒孩子，你一點也不笨，我來為大家科普一下關于激勵孩子成長的良言妙語?以下内容希望對你有幫助!激勵孩子成長的良言妙語孩子,你仍然很棒。孩子，你一點也不笨。告訴自己：“我能做到”。我很欣賞你在××方面的才能... 2022-06-10
生活抗老護膚品哪個牌子好用
要說起現在最火的護膚方式，那麼抗老護膚一定位列其中。特别是近兩年湧現出了很多新的抗老護膚形式，比如抗氧化抗初老、早C晚A護膚等，似乎大家都開始了抗老護膚。不過也正是由于抗老護膚的興起，近兩年護膚翻車的例子越來越多：因為盲目抗老護膚，導緻冷熱... 2022-10-29
生活熬夜也要追的四部劇
去年的白玉蘭獎，恐怕是江疏影從業這麼多年來，遇見的最尴尬的事情。是這樣的，江疏影去年有兩部劇播出，一部是大火的《三十而已》，江疏影是一番女主角，另一部是江疏影首次擔任女主角的古裝劇《清平樂》，是赫赫有名的正午陽光制作的劇集，這兩部劇江疏影很... 2023-02-13
生活夫妻是什麼樣的血型孩子才是o型血
對于我們每個人來說，在我們是孩童的時候，每個人就有每個人的血型，或是A型、或是B型、或是AB型、或是O型血，當然還有那麼一些極特殊的血型，例如RH陰性血，也就是我們常說的“熊貓血”。不過，這樣的人還是極少數。在現在來說，我們最多的是A型和B... 2022-11-11
生活白茶正确泡法和步驟
本文是頭條号“小陳茶事”原創文章，首發頭條号，未經允許，不得轉載!文/小陳茶事《01》周末一到，約茶的朋友不少。在這個初夏的季節，喝茶是周末打消時間最好的選擇。此刻，你可尋一處僻靜的小院子，叫上一壺茶，最好是老白茶，就能開啟愉悅的周末飲茶時... 2022-11-15
生活塞翁失馬焉知不是福
塞翁失馬焉知不是福?有時候看事情，要看他的兩面性也許你失去的同時也得到了什麼，，我來為大家講解一下關于塞翁失馬焉知不是福?跟着小編一起來看一看吧!塞翁失馬焉知不是福有時候看事情，要看他的兩面性！也許你失去的同時也得到了什麼，比如！新疆的疫情... 2022-11-10
生活禹字五行屬什麼的
禹字五行屬什麼的?禹五行屬什麼：土禹〈名〉(象形小篆字形本義：蟲名《說文》：“蟲也”一說為齲蟲)遠古夏部落領袖[thereputedfounderoftheXiaDynasty]姒姓，名文命，鲧之子禹、湯被之矣(禹、湯(都)遭受過傳說夏禹曾... 2022-07-10
生活武漢話方言教學小孩子
武漢話博大精深，特别是和其他語言對比的時候就曉得了，武漢話一出口，分分鐘可以毀掉所有畫面....普通話翻譯版關于扯皮普通話版：被你吓到了，還敢跟我搶男人武漢版，看圖說話...【關于放狠話】普通版：不要吓我，打你的武漢版，看圖說話...還有挎... 2022-11-29
生活怎麼防止鳥吃小麥
怎麼防止鳥吃小麥?找一個稻草人，最好自己動手做一個稻草人，幾個木頭，然後套幾件不穿的衣服，和一頂帽子，今天小編就來聊一聊關于怎麼防止鳥吃小麥?接下來我們就一起去研究一下吧!怎麼防止鳥吃小麥找一個稻草人，最好自己動手做一個稻草人，幾個木頭，然... 2022-06-18
生活泸州最适合旅遊的地方
春寒料峭已成過往轉眼之間泸州已是春意盎然，百花盛開安逸給大家準備了春遊攻略趁着大好春光和家人朋友來一場與春日的邂逅吧~百花浪漫盛放花田酒地桃之夭夭，灼灼其華溫暖的四月置身于花田酒地感受五顔六色的鮮花芬芳撲鼻、沁人心脾你可以肆意綻放你的笑容揮... 2022-11-04
生活制作面疙瘩的方法
制作面疙瘩的方法?将西紅柿去皮(去皮方法：沸水中煮一下或火上烤一下都很容易去掉)，切成丁，炒鍋放少許油燒熱，放入西紅柿丁和蔥花(蔥白部分)；，現在小編就來說說關于制作面疙瘩的方法?下面内容希望能幫助到你，我們來一起看看吧!制作面疙瘩的方法将... 2022-06-27
生活肇事逃逸後第二天自首會被拘留嗎
在發生交通事故的時候，肇事的車主一時過于害怕，就逃離了現場。後來經不住個人良心的譴責，也害怕逃亡生活，就積極地去公安機關自首了。那麼這類交通肇事逃逸後又自首情況如何處罰？《關于處理自首和立功若幹具體問題的意見》中規定，“交通肇事逃逸後自動投... 2022-12-16
生活一分保障十分保護
一分保障十分保護?來源：大衆新聞“買錯保險了想退保”“保險交了幾年,沒病沒痛的感覺浪費,想退保”“這款産品性價比不算太高,想退保重買”……每天都會有人因這樣那樣的原因想退保,但稍微對保險有了解的人都知道:保險想退就能退,但退多少現金價值說了... 2022-11-22
生活兩線平行同位角相等這句話有錯嗎
先看下面這道期末考試題：平行線的性質，我們很熟悉的“内錯角相等”，還有一條“同旁内角互補”，有些同學就忽略了。, 2022-12-03
生活烏冬面汁的制作方法
烏冬面汁的制作方法?材料：烏冬面200克、削過皮的胡蘿蔔1～2個、甜洋蔥4個、條狀蘑菇一包或傘狀蘑菇6～8枚、蝦仁，今天小編就來聊一聊關于烏冬面汁的制作方法?接下來我們就一起去研究一下吧!烏冬面汁的制作方法材料：烏冬面200克、削過皮的胡蘿... 2022-06-19
生活冬天适合煲哪些簡單的家常湯
自打入秋以來，家裡就喜歡煲湯喝，尤其是各種藥膳湯都是我們南方人的最愛。最近菜市場裡經常見到有新鮮的蓮子喝一些幹蓮子賣，每次都會買一些回來煮糖水或者是煲湯喝，家人都特别喜歡。這裡要分享的一道适合秋冬季節食用的湯就是用的蓮子加上蟲草花一起跟雞肉... 2022-12-19
生活油爆黑虎蝦怎麼做
油爆黑虎蝦怎麼做?食材：黑虎蝦14隻、蒜少許、生姜适量、料酒适量、紅辣椒4個、醋少許、糖适量，我來為大家講解一下關于油爆黑虎蝦怎麼做?跟着小編一起來看一看吧!油爆黑虎蝦怎麼做食材：黑虎蝦14隻、蒜少許、生姜适量、料酒适量、紅辣椒4個、醋少許... 2022-06-05
生活魔芋為什麼會麻手
魔芋為什麼會麻手?魔芋當中含有一種生物堿成分，這種成分接觸皮膚後會對皮膚造成刺激性，如果皮膚碰到魔芋當中的黏液的話，就容易引發皮膚瘙癢、紅腫等情況，現在小編就來說說關于魔芋為什麼會麻手?下面内容希望能幫助到你，我們來一起看看吧!魔芋為什麼會... 2022-08-16
生活古茗事件
讓人不可思議的事情發生了，繼明星與主播後，奶茶店也塌房了。據天眼查顯示，近期，古茗奶茶關聯公司浙江古茗科技有限公司被台州市稅務局罰款1161萬餘元。随後，相關話題在社交平台上發酵。任何表情都不足以表達，奶茶愛好者的失望，“古茗幹這樣的事，對... 2022-11-09
生活晚安撩人情話100句暖心
1、想和你重新認識一次，從你叫什麼名字開始。2、喜歡就在一起吧，别辜負了相遇。3、恰到好處的喜歡最舒服，你不用多好，我喜歡就好，我沒有很好，你不嫌棄就好。4、你的一生我隻借一程，這一程便是餘生。5、夏天遇見冰棍，冬天遇見紅薯，燒烤遇見啤酒，... 2022-11-18

tft每日頭條

> 生活

> 計數原理的簡單方法

計數原理的簡單方法

相关生活资讯推荐

热门生活资讯推荐

网友关注