夏晓光(loveJY)的博客

可能不经典啊可能不qwq

之前好多题啊没有计数标签qwq

直接扒拉我博客吧就不放链接了!

1. bfs和深度的关系是每一层一个深度

那么也就是说我们将bfs序分段一层就对应了一个深度

有的题目还要和dfs序放在一起考虑

NOI2012树的计数

2. k次交换下变成1~n排列个数

这个问题有很乐色的dp方法

$f_{i,j}$表示长度为i的排列交换j次才能得到1~n

转移考虑第i个位置插在哪里即可,不赘述,长得很像斯特林数

3. AC自动机类型:某些串的母串

计数方法一般和AC自动机上的走匹配边dp有关

具体的,如果我们要计算至少包含了某些串的母串个数,你会发现我们有用信息不是整个母串而是AC自动机上匹配的节点是那些,这个问题可以容斥/汗

4. 容斥dp

这个其实最近做过不少题,是一种固定的套路

对于$\sum_{S \subset T}(-1)^{|S|}f(S)$

这样的容斥式子,直接做是$n^2$的

但是如果内层的$'S'$关键信息很小的话(即不管选的集合是啥,总之算出的值要求很低)

可以把他们写入dp状态中,然后用dp求出在这个系数意义下其他和这个无关的系数的和

可以发现这个还包括一个方案数的系数啊

$AT4352 [ARC101C] Ribbons on Tree$

重返现实,氪金手游,猎人杀,百鸽笼等等重口题都是容斥dp

关键在于写出容斥式子,如果是可以二项式反演就不用老人家出场了

5. 树上相邻节点颜色不同

或者是一类类似的问题,他们之和树上相邻节点的信息相关

易设计树形dp,$f_{i,S}$表示考虑了i为根的子树,然后点i的信息是什么这样一个最大方案数

转移只需要考虑儿子中有没有满足什么限制即可

相邻不同色,相当于一个对于一个状态转移总方案数要扣掉儿子这个颜色的方案数

是可以$O(n*c)$的,c是颜色数

6. 数位dp计数题

这种题一般来讲可以直接设计满足限制的dp状态来统计答案

但总会有我们记不了的信息,此时可以考虑在外层花费一点代价枚举一些信息再跑这个数位dp,比如只统计digit=x的答案

我们也有一些转换算贡献的经典方法,比如方案数*权值和,或者原本我们是一列一列算的,现在变成一行一行算,具体的就是类欧里面那个变形,变成枚举答案,然后有多少他大于等于多少

7. 突然不会堆计数

即n个点的大根堆方案数

堆是完全二叉树,所以我们不难得到n个点的堆对于1号点做根后左子树有多大右子树有多大

然后我们组合数乘上左子树和右子树内部的方案就是答案

递归左右子树即可

好像向未来转移很巧妙

还有一个做法

答案等价于树的拓扑排序的数量

$\frac{n!}{\prod_{i}s_i}$

因为相当于儿子在全排列中一定要在全子树前面

所以就做完了

ZJOI2010排列计数

8. 错排问题的二项式反演

恰好有x个位置,可以转换成至少有x个位置-至少有x+1个位置+至少有x+2个位置...并且乘上对应组合系数

而至少在本问题中很好解决,相当于钦定i个位置一定放上去,然后剩下位置阶乘即可

至多的转换?

恰好x个等于恰好n-x个不合法

然后至多n-x个不合法-至多n-x-1个不合法.....

9. 互不影响的部分可以分开算然后乘起来

P6075 [JSOI2015]子集选取

这道题做法就是考虑每个元素本质相同,所以$2^n$任意组合是可以的

同时,我们有对于一种元素,他填入这个三角形方阵的方案等价于一条分割线,左上方的都有这个元素右下方的都没有这个元素

直接走就好了,每一步可以向下或者向上,这个分割线就是$2^k$