【独立计数，快速幂】P6075 子集选取

题意概括

在一个边长为 $k$ 的三角形中放置若干个集合 $A\_{i,j}$。

每个集合都必须是 $S={1,2,\ldots,n}$ 的子集，并满足向左和向上包含：

$ A\_{i,j}\subseteq A\_{i,j-1}, \qquad A\_{i,j}\subseteq A\_{i-1,j}. $

需要统计所有合法的集合放置方案数，答案对 $10^9+7$ 取模。

由于 $n,k\le 10^9$，不能枚举集合或三角形中的位置，必须推导出答案公式。

样例分析

当 $k=2$ 时，三个集合之间的关系为

$A\_{1,1}\supseteq A\_{2,1}\supseteq A\_{2,2}.$

对于任意一个元素，它有四种出现方式：

1. 三个集合中都不出现。
2. 只出现在 $A\_{1,1}$。
3. 出现在 $A\_{1,1},A\_{2,1}$。
4. 三个集合中都出现。

因此一个元素有 $4=2^2$ 种选择。

样例中有两个元素，它们的选择互不影响，所以答案为

$4^2=16.$

算法思路

不同元素相互独立

对于每个元素 $x\in S$，只需要确定它是否属于每个 $A\_{i,j}$。

集合之间的包含关系等价于：

如果 $x\in A\_{i,j}$，那么在对应位置存在时，必须同时满足

$x\in A\_{i,j-1}, \qquad x\in A\_{i-1,j}.$

一个元素的出现情况不会影响其他元素。因此，只要算出单个元素有多少种合法出现方式，再将结果取 $n$ 次方即可。

每一行都是一个前缀

固定一个元素 $x$。

由于

$A\_{i,j}\subseteq A\_{i,j-1},$

如果 $x$ 出现在第 $i$ 行的第 $j$ 个集合中，那么它也一定出现在这一行前面的所有集合中。

因此，第 $i$ 行中包含 $x$ 的位置一定构成一个前缀。

设这个前缀的长度为 $p\_i$，则

$0\le p\_i\le i.$

例如 $p\_i=3$ 表示 $x \in A\_{i,1},A\_{i,2},A\_{i,3}$，但不属于这一行后面的集合。

统计前缀长度序列

设 $f\_{i,j}$ 表示处理完前 $i$ 行，并且第 $i$ 行前缀长度为 $j$ 的合法方案数。

当 $0\le j\<i$ 时，第 $i$ 行前 $j$ 个位置都包含 $x$。根据竖直方向的包含关系，第 $i-1$ 行至少也要包含前 $j$ 个位置。

所以前一行的前缀长度 $t$ 必须满足 $t\ge j$，得到

$

f_{i,j}

\sum_{t=j}^{i-1}f_{i-1,t}. $

当 $j=i$ 时，第 $i$ 行全部位置都包含 $x$。前 $i-1$ 个位置在上一行都有对应位置，所以第 $i-1$ 行也必须全部包含 $x$：

$f\_{i,i}=f\_{i-1,i-1}=1.$

下面证明

$ f\_{i,j}= \begin{cases} 2^{i-j-1},&0\le j\<i,\\ 1,\&j=i. \end{cases} $

初始时 $i=1$，第一个位置可以不包含或包含 $x$，因此

$f\_{1,0}=f\_{1,1}=1,$

符合公式。

假设第 $i-1$ 行的公式成立。对于 $j\<i$，有

$ \begin{aligned} f\_{i,j} &=\sum\_{t=j}^{i-1}f\_{i-1,t}\\ &=\sum\_{t=j}^{i-2}2^{i-t-2}+1\\ &=2^{i-j-1}. \end{aligned} $

因此公式对所有行成立。

处理完前 $i$ 行的总方案数为

$ \begin{aligned} \sum\_{j=0}^{i}f\_{i,j} &=\sum\_{j=0}^{i-1}2^{i-j-1}+1\\ &=(2^i-1)+1\\ &=2^i. \end{aligned} $

所以一个元素在边长为 $k$ 的三角形中共有

$2^k$

种合法出现方式。

计算总答案

集合 $S$ 中共有 $n$ 个元素，每个元素都可以独立选择一种合法出现方式。

因此总方案数为

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

最终只需要使用快速幂计算

$2^{nk}\bmod 1000000007.$

算法流程

1. 读入 $n,k$。
2. 计算指数 $nk$。
3. 使用快速幂计算 $2^{nk}\bmod 1000000007$。
4. 输出结果。

正确性说明

对于任意一个元素 $x$，水平方向的包含关系保证它在每一行中的出现位置构成前缀。

状态 $f\_{i,j}$ 枚举了第 $i$ 行前缀长度为 $j$ 的所有情况。转移要求上一行的前缀覆盖当前行中具有上方对应位置的所有元素，因此转移得到的方案全部合法。

反过来，任意合法出现方式在每一行都有唯一的前缀长度，因此会唯一对应到一条状态转移路径，不会遗漏，也不会重复统计。

由状态递推可知，一个元素共有 $2^k$ 种合法出现方式。不同元素的成员关系彼此独立，将每个元素的出现方式组合起来，可以唯一确定所有集合。因此总方案数为

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

快速幂计算的正是该值对 $10^9+7$ 取模后的结果，所以算法正确。

实现细节与易错点

$n$ 和 $k$ 最大都是 $10^9$，因此指数 $nk$ 最大为 $10^{18}$，必须使用 long long 保存。

不需要利用费马小定理缩小指数。快速幂的循环次数只有

$O(\log(nk)),$

可以直接处理 $10^{18}$ 级别的指数。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll md = 1000000007;

ll qp(ll a, ll b) {
    ll r = 1;
    while(b) {
        if(b & 1) r = r * a % md;
        a = a * a % md;
        b >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, k;
    cin >> n >> k;

    cout << qp(2, n * k) << '\n';
    return 0;
}

复杂度分析

快速幂需要处理指数 $nk$，时间复杂度为

$O(\log(nk)).$

只使用常数个变量，空间复杂度为

$O(1).$