子集选取：题解

思路

把集合约束拆成元素约束

固定一个元素 $x\in S$，只关心它是否属于每个 $A_{i,j}$。集合包含关系逐元素成立，所以不同元素之间没有耦合：先求一个固定元素有多少种合法的出现模式，再把这个数量取 $n$ 次方即可。

对固定元素，把“属于”记为 $1$，“不属于”记为 $0$。若某格为 $1$，它有效的左邻格、上邻格也必须为 $1$。因此每一行中的 $1$ 必然构成一个前缀。

做法

统计单个元素的模式

令 $d_{i,r}$ 表示前 $i$ 行合法，并且第 $i$ 行恰有前 $r$ 格为 $1$ 的模式数，其中 $0\le r\le i$。

当 $r<i$ 时，上一行的前缀长度 $s$ 可以是任意 $s\ge r$，因此

$$d_{i,r}=\sum_{s=r}^{i-1}d_{i-1,s}.$$

当 $r=i$ 时，本行全为 $1$，上一行也必须全为 $1$，故

$$d_{i,i}=d_{i-1,i-1}=1.$$

由 $d_{1,0}=d_{1,1}=1$ 出发归纳，可以得到

$$d_{i,r}= \begin{cases} 2^{i-r-1},&0\le r<i,\\ 1,&r=i. \end{cases}$$

把最后一行的所有前缀长度求和：

$$\sum_{r=0}^{k}d_{k,r} =\sum_{r=0}^{k-1}2^{k-r-1}+1 =2^k.$$

所以，一个固定元素恰有 $2^k$ 种合法出现模式。

合并所有元素

$S$ 中的 $n$ 个元素有标号，且每个元素的出现模式可以独立选择。一个完整方案又能唯一恢复每个元素的模式，所以根据乘法原理，方案总数为

$$(2^k)^n=2^{nk}.$$

最终对 $1{,}000{,}000{,}007$ 取模。由于 $n,k\le10^9$，乘积 $nk\le10^{18}$，必须用有符号64位整数保存指数，再执行二进制快速幂。

复杂度

时间复杂度为 $O(\log(nk))$，空间复杂度为 $O(1)$。

部分分算法

当 $k\le2000$ 时，可以不使用分布闭式，直接维护当前行各前缀长度的方案数，并以一遍后缀和完成下一行转移。总状态数为 $O(k^2)$，空间可滚动为 $O(k)$。得到单元素模式总数后，再对其取 $n$ 次幂。

当 $k\le10^7$ 时，可以使用“单元素模式数每增加一行翻倍”的递推，循环 $k$ 次求出 $2^k$，再快速计算它的 $n$ 次方。复杂度为 $O(k+\log n)$。

满分算法把两次幂直接合并为 $2^{nk}$，避免任何关于 $k$ 的线性循环。

边界与周期

• $n=1$ 时答案为 $2^k$。
• $k=1$ 时只有一个任意子集，答案为 $2^n$。
• 样例 $n=k=2$ 时答案为 $2^4=16$。
• 模数是质数，答案永远不为 $0$。
• 若主动约去指数周期，应对 $1{,}000{,}000{,}006$ 取模，不能对模数本身取模。