Solution - P6075 [JSOI2015]子集选取

P6075 [JSOI2015]子集选取

idea:

数学

解决方案：

这道题是真的不简单，不知道为什么只是一个黄题。

首先，我们枚举每个位置放什么是非常麻烦的，于是我们可以把问题转化成把 $1...n$ 这 $n$ 个数放到哪些位置。显然 $1...n$ 都是等价的，于是我们先研究 $n = 1$ 的情况，最后在乘个 $n$ 次就好了。

我们发现，其实每种放法都会形成一条分割线，分割线以上都是 $1$ 分割线以下都是 $0$ 。我们不妨枚举分割线上面的 $1$ 的位置（即最下端的 $1$ ）。

如果分割线是从第 $i$ 行的最左端开始的，那么这个分割线需要走 $i-1$ 步才能到达右端（只能往上和往右走）。每步都有两种选择（上和右），故答案是 $2^{i-1}$ 。故最终答案是 $\sum_{i=1}^k 2^{i-1}$ 加上全部都是 $0$ 的一种情况，刚好是 $2^k$ 。

故最终答案为 $2^{k\cdot n}$ 。