アリ！？ナシ！？ ナシ！？アリ！？
ついてる ついてない あれどっち？どっち？Trance, trance, trance
蟻！？梨！？ nAシ！？ァ理！？
自我 字が 崩壊！
インドア警備隊 紫外線さよなら
(バイバイ alright! 一級在宅 allday!)
やる気の“や”の字 どっかにいっちゃったんだ
ナイナイ 心技體 実家に帰ります)
ああ 未知なる世界と目があったよ
微笑んで 手招きしてるの
ねえ こっちの水はスウィーツパラダイス
おしゃれ メイク ヘアアレンジ
乙女の園で ダンスした
あれ わたし(Who!)
誰(Are!)
オレOleお？((It’s me!)
知らない 何 壊れそうな アイデン貞貞
産まれたばかり a sense of wonder
そのまま maybe 溶けてゆく 深層心理
目覚め
たまえ
眠れるアイツ
いくとこまで いってみようか ハッピーエンド？
アリ！？ナシ！？ ナシ！？アリ！？
ついてる ついてない あれどっち？どっち？Trance, trance, trance
蟻！？梨！？ nAシ！？ァ理！？
自我 字が 崩壊！
おさんぽ調査団 瀕死でおかえり
へイへイ fall down! 三流散策 weekend!)
やる気を出した 結果が大変だった
(累々 死屍die! ファイト一発)
ああ マジカルウルトラスーパーミラクル
抱きしめて 慰めてくれよ
ええ そんなの夢さ ドリームワンダーランド
地道 努力 コツコツ
正論マンが パンチした
やれ右(Uh!)
右(Hah!)
左右！(ワンツー！)
いらない 愛つよがりな アイデン貞貞
素直になりなさい catch on fire
わがまま baby 解けてゆく 固定観念
ふるい
たまえ
內なるケモノ
自分自身を知るための 決闘だ
白か黒かで決めた(オセロ！)
0か100しかないの？(極論！)
生きづらい俗世だね(娑婆ばい！)
神様 仏様 この私目にお導きを...
それでいいのか(YES! NO!) アイデンティティよ
目を覚ませ！

sosdp,FMT,FWT 上

FWT 和一些難點的題放到下次寫。

sosdp

首先考慮最基本的問題：

定義集合 \(U\subseteq R,X=\{S|S\subseteq U\}\)，定義函數 \(f:X\to R,g(S)=\sum\limits_{T\subseteq S} f(S)\)，對于所有的 \(S\in U\) 求 \(g(S)\)，\(n=|U|\le22\)

首先暴力枚舉 \(S,T\) 是 \(n^4\) 的，考慮優化。

1. 子集枚舉：

   考慮將集合抽象成二進制，求 \(S\) 的子集相當于枚舉其所有掩碼，有代碼：

   for(int t=s;t;t=(t-1)&s)
   

   這里 \(t\) 是 \(s\) 的子集。解釋就是 t-1 每次將 t 最后一個一置零，后面全置一，與上 \(s\) 可以去除掉多余部分，顯然 \(t\) 降序遍歷 \(s\) 掩碼。

   暴力枚舉 \(s\)，復雜度是 \(3^n\) 的。

2. 高維前綴和：

   我們發現子集枚舉并沒有很好的利用信息之間的可合并性，發現將二進制每位拆成一維，其相當是高維前綴和，有代碼：

   for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if(j>>i&1) f[j]+=f[j^1<<i];
   

   解釋：考慮求二維，三維，四維前綴和時，有簡單的做法是每次枚舉一維做前綴和，其實代碼就是在枚舉第 \(i\) 維和當前狀態 \(j\)，在加上去。

   復雜度 \(n2^n\)

沒錯，這就是 sosdp，其實就是遞推求前綴和。

會了前綴和還要會差分，容易想到將循環變向，加變減即可，考慮到每維的大小只有 \(2\)，所以循環反不反向都無所謂啦。

高維后綴和、差分也類似，考慮其是把 \(1\) 加到零上，將 if(j>>i&1) 改成 if(!(j>>i&1)) 就好了。

先就此打住，做一個還算有點意思的板子：CF449D Jzzhu and Numbers

快速莫比烏斯變換（FMT）

注意和莫比烏斯變換區分。

板子：

給定兩個集合上的函數 \(f,g\) 求 \(h(S)=\sum\limits_{I\circ J = S} f(I)*g(J)\)，其中 \(\circ\) 可以是 \(\cup\) 和 \(\cap\)。

考慮先做并，先對 \(f,g\) 做前綴和，在計算 \(h'(S)=f(S)*g(S)\)，然后對 \(h'\) 做前綴差分，根據定義，其就是 \(h\)。

雖然我并不會 FTT，但不影響題解讓我發現，這個操作和 FTT 的 DFT 很像——同樣是對一個函數作運算得到另一個函數，然后用運算完的操作進行按位求積，最后再進行反向操作將其變換為原函數。而整套流程下來，實現了卷積的效果，所以這個也叫 OR 卷積，在原函數和新函數間建立雙射的操作，被稱作“快速莫比烏斯變換 Fast Mobius Transform(FMT)”。

類似可以做 AND 卷積，用后綴操作代替前綴，可以解決交的問題。

復雜度是 \(n2^n\)，但是考慮設 \(n\) 表示 \(S\) 的總方案數，在一般的二進制中就是原數的大小，復雜度是 \(n\log n\) 的——和 FFT 一樣。

與 AND 和 OR 類似的，其實 XOR 的卷積也是可以做的，但是要用到 FWT，并且因為其結構更像 FFT，因此更難寫。