[JSOI 2015] 子集选取

题目大意

给定包含 $n$ 个元素的集合 $S$ 和一个正整数 $k$ ，选出 $S$ 的若干子集 $A_{i, j} \; (1 \leqslant i \leqslant j \leqslant k)$ 排为如下的三角形：

\begin{align} &A_{1, 1} \\ &A_{2, 1} &A_{2, 2} \\ &A_{3, 1} &A_{3, 2} &A_{3, 3} \\ &\dots \end{align}

满足 $A_{i, j} \subseteq A_{i, j - 1}$和$A_{i, j} \subseteq A_{i - 1, j}$。求子集选取的方案数，答案对 $1,000,000,007$ 取模。

$1 \leqslant n, \; k \leqslant 1,000,000,000$

题目链接

【JSOI2015】子集选取 - Luogu 6075

题解

毕姥爷在 WC2017 上讲过的题。

对于每个元素，它只能出现在三角形的左上角。从三角形的左下角开始，要么向上，要么向右，走 $k$ 步形成一条分割线，左上是含该元素的，右下不含该元素。分割线的情况是 $2^k$，每个元素相互独立，答案乘起来，即 $2^{k n}$，用快速幂计算。

代码

#include <cstdio>
const int MOD = 1000000007;
long long pow(long long a, long long n) {
    long long res = 1;
    for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
    return res;
}
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%lld\n", pow(2, (long long) n * k));
    return 0;
}