BZOJ4475 [JSOI2015] 子集选取

Description

有一些{1n}\{1\dots n\}的子集Ai,j,1jikA_{i,j}, 1\leqslant j\leqslant i\leqslant kk(k+1)2\frac{k(k+1)}2个,满足Ai,jAi+1,j,Ai,jAi,j+1A_{i,j}\subset A_{i+1,j}, A_{i,j}\subset A_{i,j+1}。求这些集合有多少种方案。如果AABB两种方案中存在i,ji,j使得Ai,jBi,jA_{i,j}\neq B_{i,j},则它们是不同的。n,k109n, k\leqslant 10^9

Solution

对于n=1n=1求出方案数,之后将这个方案数取nn次幂即可。因为不同的元素之间是互不影响的。

n=1n=1时,我实际上要从

A1,1A2,1A2,2A3,1A3,2A3,3Ak,1Ak,2Ak,3Ak,k\begin{matrix} A_{1,1}\\ A_{2,1}&A_{2,2}\\ A_{3,1}&A_{3,2}&A_{3,3}\\ \vdots&\vdots&\vdots&\ddots\\ A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k} \end{matrix}

这个三角中选出一些来包含11

那么,我从这个矩阵左下角即Ak,1A_{k,1}的左下方开始,每次向右或上走一步,直到某个Ai,iA_{i,i}的左上角(或者Ak,kA_{k,k}的右下角);走出这个折线的右下的集合包含11,其它不包含11。那么我一共会走(ki+1)+(i1)=k(k-i+1)+(i-1)=k步,每步可以向右/下走,所以共有2k2^k种方案。

综上,答案即为2nk2^{nk}

Code

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
typedef long long LL;
const int mod = 1000000007;
int main() {
int n, k;
scanf("%d%d", &n, &k);
int ans = 1, x = 2;
for (n = (LL)n * k % (mod - 1); n; n >>= 1, x = (LL)x * x % mod)
if (n & 1) ans = (LL)ans * x % mod;
return printf("%d\n", ans) & 0;
}