简单计数题选做

题单

后面的似乎都得生成函数。。。所以就做了最简单的一些

P6146 [USACO20FEB]Help Yourself G

显示解法

之前做过,已经忘了怎么做了,再做一次

假设我们直接做,考虑每一次新加入一条线段会产生怎样的贡献

发现可能会合并一些段,然后增加一些段,还有原来的贡献

我们考虑所有线段按左端点排序,那么就不会产生合并

那么只需要考虑新的贡献,不难发现就是只选所有与当前线段不交的线段的方案数,发现是 $2^k$ 的形式

这个可以前缀和处理

复杂度 $\mathcal{O}(n \log n)$,瓶颈在 $\mathcal{O}(n)$ 次快速幂

所以用光速幂就是 $\mathcal{O}(n)$

P6075 [JSOI2015]子集选取

显示解法

只考虑每一个元素在每一个集合中的存在性,显然最后只需按照乘法原理全部乘起来即可。

考虑对于一个元素,一定存在一条分界线,两边一边全取一边全不取

可以考虑从左下角开始走,不难发现走 $n$ 步恰好到达边界

因此答案就是 $2^{nk}$

P6008 [USACO20JAN]Cave Paintings P

显示解法

首先不难发现每一个连通块相互独立

其次注意到我们若从下往上 DP,那么对于一个连通块,当前层若选,则是只有一种方案,否则就是所有下一层的块按乘法原理算出来的总方案

因此用并查集维护连通性,合并的时候贡献,最后每一个连通块 +1 即可

答案就是所有连通块的答案乘起来

P1350 车的放置

显示解法

考虑直接用组合数来放

先放高的部分,考虑枚举选出 $t$ 列放东西,那么低的部分就要选出 $k-t$ 列,显然这两部分都是可以算的,乘上一个 $\binom{a}{t}$ 和一个 $\binom{c}{k-t}$ 就行了

然后再枚举额外区域放 $s$ 个,那么我们 $\binom{t}{s}$ 列放高的,然后高的部分选 $b^{\underline{s}}$

剩下共 $k-s$ 放低的,左边的列已经选好了因此再乘上一个 $d^{\underline{(k-s)}}$ 就行了

P3205 [HNOI2010]合唱队

显示解法

根据末尾状态的变化,可以区间 dp

设 $f_{i,j,0/1}$ 表示区间 $[i,j]$ 还有最后一个人进来的方向

状态设出来之后转移就比较显然了

P4071 [SDOI2016]排列计数

显示解法

发现选出所有匹配位置之后剩下的就是一个全错位排列

因此递推然后直接乘起来就行

P3223 [HNOI2012]排队

显示解法

小奥,懒得写