今天集訓的題我已經寫不動了，下周開始會復習 dp, 現在就提前把一些東西補一補，這個說不好會在之后狀壓里邊用到。

枚舉子集

如何遍歷一個集合的子集

通常我們會采取遞歸的方式，是 \(O(2^n)\) 的，但是這個樣子我們在具體使用的時候是很不方便的，尤其是我們在對于一些二進制的東西做文章的時候。

所以我們需要這個循環形式的枚舉子集。

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

這個樣子我們就是在枚舉 \(s\) 為 \(u\) 的子集了。

先談正確性，后談復雜度。

為什么這個東西可以不重不漏？

很明顯的，我們的減一是嚴格下降的，按位與是嚴格不升的，每一次操作必然會變小，故不會重復。

至于正確性，我們的減一實際上是刪除 s 中最后一個一，再把它的右邊全部變成一。我們為了讓這個東西變成新的子集，我們需要刪除 u 之中沒有包含的 1,這個我們直接按位與清除一下就好啦。

時間復雜度就是明顯的了，我們僅僅需要關注 1 的數量，復雜度自然是 \(O(2^{popcount(u)})\)。

如何遍歷一個集合子集的子集

for(int m=0; m<(1<<n); ++m){
	for(int s=m; s; s=(s-1)&m){
		......
	}
}

也就是直接套用上邊的。

這個東西的復雜度是奇妙的，它竟然是 \(O(3^n)\) 的，比我們想象中要底很多很多。

如果 \(m\) 擁有 \(k\) 個 \(1\)，那么我們會枚舉出來 \(2^k\) 個子集。

而對于一個 \(k\)，我們可以找出來 \(\binom{n}{k}\) 個對應的集合滿足有 \(k\) 個 1。

總數就變成了：\(\sum_{k=0}^{n}\binom{n}{k}2^k\)。

根據二項式定理，這個東西等于 \((1+2)^n\) 的展開，因此是 \(O(3^n)\) 的，似乎很有用，避免了我們傻傻的 \(2^n\times 2^n\) 的枚舉。

高維前綴和

又稱 sosdp，我不知道為什么。

我們平常做一維或者二維前綴和都是用容斥原理求的，以二維為例。

\(sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]\)。

但是我們還有一個求法，就是一維一維處理。

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i][j - 1];

like that.

這個樣子是一樣的，我們采取這個思路。

對于求解 \(0\le i\le 2^n-1\)，\(\sum_{j\in i} a[j]\) 這樣的東西，我們可以使用這個思路。

我們不妨把集合看作多維空間中的點，第 \(i\) 位的 0/1 表示第 \(i\) 維的坐標。

于是乎就可以像之前那么做了，枚舉維數與子集，在當前維度是 1 的地方從當前維度是 0 的地方轉移過來。

for(int i=0; i<n; ++i){
	for(int j=0; j<(1<<n); ++j){
		if(j&(1<<i)) dp[j]+=dp[j^(1<<i)];
	}
}

于是就沒有了，顯然我們從枚舉子集的 \(O(3^n)\) 優化到了 \(O(n\times 2^n)\)。