03-30

SOS dp

前置知識

簡單dp，循環，二進制。

應用范圍

高維前綴和，子集和，超集和，FWT。

思路

我們以高維前綴和(注意每一位只有0/1)為例來思考。

高維前綴和

先給出一維前綴和的形式的求法。

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

二維前綴和（非容斥寫法，但是顯然正確）的求法

for(int i=1;i<=n;i++)
   	for(int j=1;j<=n;j++)
        sum[i][j]+=sum[i][j-1];//可以理解為先處理出列的前綴和
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        sum[i][j]+=sum[i-1][j];//再處理行的前綴和。

我們可以受到啟發，一維一維的處理答案。首先，因為每一維只有 \((0,1)\) 所以我們可以狀壓。我們設 \(f_{i,s}\) 表示處理了前 \(i\) 維狀態為 \(s\) 的答案。我們考慮轉移，如果這一維是 \(1\) ，有 \(f_{i,s}=f_{i-1,s}+f_{i,s\oplus(1<<i)}\) 。什么意思？我們現在和二維的情況是一樣（前面 \(i-1\) 處理完了合起來看，當前處理的這一維），加 \(f_{i,s\oplus(1<<i)}\) 表達就是第 \(i\) 維的前綴和（\(1\) 的情況加上 \(0\)），\(f_{i-1,s}\) 表示就前 \(i\) 維的前綴和（這一維加前 \(i-1\) 維）。如果這一維是 \(0\) 的話，就直接從 \(f_{i-1,s}\) 轉移即可。滾掉第一維后，可以寫出以下的代碼。

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

我再說一點我當時覺得難以理解的地方是 dp 狀態 \(s\) ,其實它就二維里的 \([i][j]\) 只是狀壓成一個數方便存儲。同時在處理前 \(i\) 維時，只用了 \(s\) 的最低的 \(i\) 維。

子集和

我們考慮知道任意一個集合 \(S\) 的答案，要求集合 \(S\) 和 \(S\) 所有子集的答案和。我們可以將每一個元素選或不選 (\(1/0\) 來表示)狀壓出的數表示 \(S\) ,我們發現 \(S\) 的子集和就是高維前綴和，因為某一維 \(S\) 有 \(1\) ,加上 \(0\) 的情況就表示 \(S\) 中有，但是不選，顯然 \(S\) 的所有子集都會被算一遍。

代碼與高維前綴和一模一樣，就不放了。

超集和

\(S\) 的超集就所有集合 \(T\) 滿足 \(S\) 是 \(T\) 的子集。

顯然現在不是 \(S\) 有 \(1\) 可以選 \(0\) 的情況，而是\(S\) 有 \(0\) ，可以選 \(1\) 的情況。將高維前綴和轉移變成當前位為 \(0\) 時加上 \(1\) 的答案。（應該叫它高維后綴和）

代碼如下。

for(int i=0;i<n;i++)
    for(int j=0;j<(1<<n);j++)//一開始對枚舉順序有疑問，按照定義應該從小到大枚舉，因為這里只有0和1，且當前1直接繼承，所以f[i-1][j^(1<<i)]與f[i][j^(1<<i)]相等
        if(!((j>>i)&1))f[j]=(f[j]+f[j^(1<<i)])%mod;

高維前綴差分

有前綴和與差分肯定是相生相伴的。所以我們考慮一個問題是我們已知集合 \(S\) 與 \(S\) 的所有子集的答案和，如何求 \(S\) 的答案。我們可以仿照前綴和定義dp，設 \(f_{i,s}\) 表示分離了前 \(i\) 維狀態為 \(S\) 的答案（分離指的是已經不包含前 \(i\) 維 \(S\) 是 \(1\) 的時候取 \(0\) 的答案）。dp轉移與前綴和相比只變了符號。