Part 1：前置知识

1、状压 DP

2、基本的位运算操作

Part 2：SOS DP

(以下的内容大部分翻译至CF上的原文 ）

1、例题引入

给定一个含 \(2^N\) 个整数的集合 \(A\)，我们需要计算：\(\forall x \subseteq A\)，\(x\) 中所有元素 \(i\) 的 \(A[i]\) 的和，即求：

2、解题思路

法一：暴力枚举

• 我们可以枚举每一个 \(mask\)，再枚举集合中的所有元素 \(i\)，判断 \(i\) 是属于集合 \(mask\)。这样做的时间复杂度为 \(O(4^N)\)

• 代码

for(int mask=0; mask<(1<<N); mask++)
  	for(int i=0; i<(1<<N); i++)
		if((mask&i)==i)
		  	F[mask]+=A[i];

法二：枚举子集

• 对于任意 \(mask\)，如果它做的二进制位上有 \(k\) 个 \(1\)，那么它就有 \(2^k\) 个子集，我们只需遍历这些子集便可。

  时间复杂度为 \(O(\sum\limits_{k=0}^{N}{\tbinom{N}{k}2^k})=O((1+2)^N)=O(3^N)\)。（可由二项式定理证明）

• 代码

for(int mask=0; mask<(1<<N); mask++)
{
	F[mask]=A[0];
	for(int i=mask; i>0; i=(i-1)&mask)
		F[mask]+=A[i];
}

法三：SOS DP

• 在我们之前的方法中存在明显的缺陷：当一个状态的二进制位上有 \(k\) 个 \(0\) 时，它将被访问 \(2^k\) 次，存在重复的计算。

  而产生这种现象的原因就是：我们没有在 \(A[x]\) 被不同 \(F[mask]\) 利用时建立一定的联系。我们应添加另一个状态来避免上述的重复计算。

• 我们定义状态 \(S(mask)=\{x|x\subseteq mask\}\)。现在我们把这个集合划分为不相交的组。

  设\(S(mask,i)=\{x|x\subseteq mask,\:mask⊕x<2^i+1\}\)，表示只有第 \(i\) 位以及更低位与 \(mask\) 不同的 \(x\) 的集合。

  举个例子：\(S(\)101\(1010,3)=\{\)101\(1010,\)101\(0010,\)101\(1000,\)101\(0000\}\) 。其中 \(1010\) 即为 \(mask\) 的第 \(3\) 位至第 \(0\) 位，集合中的元素的加粗部分应与 \(mask\) 保持一致。

• 现在让我们尝试将 \(mask\) 与 \(x\) 建立联系，下面分两种情况讨论：

  1. \(mask\) 的第 \(i\) 位是 \(0\)

     不难发现，\(mask\) 与 \(x\) 的第 \(i\) 位均为 \(0\)。因此 \(x\) 仅有第 \(0\) 至 \(i-1\) 位与 \(mask\) 不同，故有 \(S(mask,i)=S(mask,i-1)\)

  2. \(mask\) 的第 \(i\) 位是 \(1\)

     那么 \(S(mask,i)\) 就由两部分组成：

     \((1)\:\) \(x\) 的第 \(i\) 位为 \(0\)，即为 \(S(mask⊕2^i,i-1)\)

     \((2)\:\) \(x\) 的第 \(i\) 位为 \(1\)，即为 \(S(mask,i-1)\)

• 综上，可以得出结论

  \[S(mask,i)=\begin{cases}S(mask,i-1)&&i^{th}\:bit \:0\\S(mask,i-1)+S(mask⊕2^i,i-1)&&i^{th}\:bit\:1\end{cases} \]

  不难计算，这种做法的时间复杂度为 \(O(N2^N)\)

• 代码（二维版）

for(int mask=0; mask<(1<<N); mask++)
{
	dp[mask][-1] = A[mask];
	
	for(int i=0; i<N; i++)
	{
		if(mask&(1<<i))
			dp[mask][i]=dp[mask][i-1]+dp[mask^(1<<i)][i-1];
		else
			dp[mask][i]=dp[mask][i-1];
	}
	
	F[mask]=dp[mask][N-1];
}

• 代码（一维版）

for(int i=0; i<(1<<N); i++)
	F[i]=A[i];

for(int i=0; i<N; i++) 
{
	for(int mask=0; mask<(1<<N); mask++)
	{
		if(mask&(1<<i))
			F[mask]+=F[mask^(1<<i)];
	}
}