「闲话随笔」套娃子集

点击查看目录
目录

为什么要写这么弱智的内容：我太菜了。

枚举子集作用

常用于状压 DP。

枚举一个状态的所有子集状态。

例如 1101 的子集有：

1101
1101
1001
1000
0101
0100
0001
0000

代码

for (ll i = u; i; i = (i - 1) & u) {
	// i 是子集
}

原理

每次 i-1 后都会把当前状态的最后一个 1 后面的所有位变为 1，这一位变为 0。

再 &u 将不能为 1 的每一位变为零，保证当前枚举的是子集。

那么当前就可以枚举到 比上一个状态小的所有状态中最大的状态。

例如枚举 1101 的子集，当前到了 1100。

进行第一步得 1011，进行第二步得 1001。

感觉讲了和没讲一样，感性理解吧。

复杂度

枚举一个状态的的复杂度显然是 \(2^n\) 的，这里主要讨论枚举 \(0\sim 2^n\) 的所有状态的所有子集的时间复杂度。

显然可得式子：

\[\sum_{i=0}^{n}\dbinom{n}{i}2^i
\]

发现很眼熟，用个谔项式定理套一下：

\[\begin{aligned}
\sum_{i=0}^{n}\dbinom{n}{i}2^i
&=\sum_{i=0}^{n}\dbinom{n}{i}2^i1^{n-i}\\
&=(2+1)^n\\
&=3^n
\end{aligned}
\]

得到了时间复杂度 \(\Theta(3^n)\)。

意义？

每一位有三种可能：

  • 当前枚举的子集和状态这一位都是 0；
  • 当前枚举的子集和状态这一位都是 1；
  • 当前枚举的状态的这一位是 1，但它的子集的这一位是 0。

乘法原理得 \(3^n\)。

套娃子集

其实刚才讨论的情况可以当成：枚举状态 \(2^n\) 的子集的子集。

那么我们考虑套娃：

\[\begin{matrix}
\underbrace{枚举状态 2^n的子集的子集\cdots的子集}\\
k个的子集
\end{matrix}
\]

时间复杂度：

\[\begin{aligned}
&\sum_{i1=0}^{n}\dbinom{n}{i1}\sum_{i2=0}^{n}\dbinom{n}{i2}\cdots\sum_{ik=0}^{n}\dbinom{n}{ik}1\\
=&\sum_{i1=0}^{n}\dbinom{n}{i1}\sum_{i2=0}^{n}\dbinom{n}{i2}\cdots\sum_{ik-1=0}^{n}\dbinom{n}{ik-1}2^n\\
=&\sum_{i1=0}^{n}\dbinom{n}{i1}(k-1)^n\\
=&k^n
\end{aligned}
\]

组合意义同上。

真是非常有趣的性质呢。

\[\Huge{\mathfrak{The\ End}}
\]