题解 P6075 【[JSOI2015]子集选取】

理解一下这道结论题。 有一篇题解说过，集合中的元素是没有关系的，所以我们只要想一下$n=1$的情况就 ok 了。假设$n=1$时的的结果为 S ，那么$n=P$时就是$S^P$~~这个感性理解一下~~。 $n=1$的情况：因为题中说，所有的集合都是其左方和右方的子集。就是上方有一些 1，下方有一些 0。如果直接计算的话不太好搞，我们通过这个分成两块的性质可以**枚举0和1的分界线**。 我们从左下角开始。这个点只有两种走法。向上或或向右。为啥？ - 假设一个子集为1，那么他左上方肯定全是1。 - 如果分界线往下走了一格，  - 这样的话1的左边是0，而不是1，矛盾 因为向上和向右有两种可能，而走 k 步才能走到边界。所以答案就是$2^k$ 总的答案就是$2^{k\cdot n}$。 结论：此题是快速幂模板题。