【TIOJ 1971】撿豆豆（Beans）

原題連結：http://tioj.infor.org/problems/1971
最近怎麼反而在練選訓題了(汗
明明根本還沒進選訓

這題一整個經典拈題
前55分有顯然的O(MN) SG Value解
比較值得提到的是後面的第三子題和第四子題

我先確定55分自己能拿之後跳過第三的12分開始想後面的33分
因為保證a_i<=20，假設我們能在這個子題實行SG Value的話
首先先觀察到所有>1的SG值都沒有用處，可以直接填上1就好了，0就還是0
於是可以觀察到，對於連續K個的區間，最多只存在2^K種區間SG
又因為第四子題a_i<=20，所以對於一個SG[i]需要呼叫的子問題絕對不低於SG[i-20]，也就是K=20
所以可以保證出現第一個重複的「大小N的區間SG」時，後面的SG結果就會和前面呈現週期性的重複
由於區間SG只有2^20種，轉換後又很方便是整數，所以可以開一個2^20的陣列紀錄每種區間SG出現的時刻
這裡還用map之類的資結絕對是中毒了(?，計算轉換的值可以邊跑邊算，所以是完完全全的O(2^N)
寫起來也不難，找到週期後記得處理一下餘數問題加前面就有88分了，似乎頗賺的(?

最讓我意外的是剩下的12分，因為我第一次拿完88分就直接卡死了只好放棄
直到最近看了某國手的文才發現，據說用O(MN)拿bitset硬開會過！？

......然後真的過了
雖然看他的文章讓我有種我可能假解了的feel，可是看在我執行時間不算久的情況下就算了(X
結論就是，bitset真強大啊OwO~~

\