Bessie正在觀察A隻螞蟻
它們可以分成T(1000)個族群、編號1...T，每個族群有1...100隻螞蟻
(也就是說A最多到100000)
Bessie想要把它們分成好多好多子集合
她想知道具有S隻螞蟻的子集合數+(S+1)螞蟻子集數+(S+2)螞蟻子集數+...+B螞蟻子集數
總共是多少？(mod 1000000)
程式碼：codepad掛了，待補
關鍵字「子集合」、「方法數」已經八九不離十，就是填表格DP搞一搞
怎麼填呢？先幻想一下有一個已經算好的母集合S，具有3個元素：
其中0,1,2,3個元素子集合的種類數假設A,B,C,D
那麼S加上一個叉叉構成的0,1,2,3,4子集方法數如下表
| 集合 | 0 | 1 | 2 | 3 | 4 |
| S | A | B | C | D | |
| S+{X} | A | B | C | D | |
| 合計 | A | A+B | B+C | C+D | D |
如果想把S加上兩個叉叉，那麼列出1個叉叉和2個叉叉的結果是
| 集合 | 0 | 1 | 2 | 3 | 4 | 5 |
| S | A | B | C | D | ||
| S+{X} | A | B | C | D | ||
| S+{XX} | A | B | C | D | ||
| 合計 | A | A+B | A+B+C | B+C+D | C+D | D |
加上三個叉叉會像是這樣：
| 集合 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| S | A | B | C | D | |||
| S+{X} | A | B | C | D | |||
| S+{XX} | A | B | C | D | |||
| S+{XXX} | A | B | C | D | |||
| 合計 | A | A+B | A+B+C | A+B+C+D | B+C+D | C+D | D |
觀察規律以後就能得到一個"某某母集S"轉移到"S+{很多叉叉}"的方法
過程中紀錄一個total值
0...3會依序把A,B,C,D給加入
然後視乎叉叉的數量，從"n-數量-1"的時候開始刪除A,B,C,D
當然了，叉叉數量越多、表示越晚開始刪除
最後記得要(x+MOD)%MOD再輸出，免得負數吃WA
沒有留言:
張貼留言