[JSOI 2015] 子集选取

题目大意

给定包含 nn 个元素的集合 SS 和一个正整数 kk ,选出 SS 的若干子集 Ai,j  (1ijk)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}

满足 Ai,jAi,j1A_{i, j} \subseteq A_{i, j - 1}Ai,jAi1,jA_{i, j} \subseteq A_{i - 1, j}。求子集选取的方案数,答案对 1,000,000,0071,000,000,007 取模。

1n,  k1,000,000,0001 \leqslant n, \; k \leqslant 1,000,000,000

题目链接

【JSOI2015】子集选取 - Luogu 6075

题解

毕姥爷在 WC2017 上讲过的题。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#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;
}