qwqUwU。

感觉很有用。

容斥

二项式定理和二项式反演直接跑。我说白了全是这坨。

\[\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c} \]

[ABC423F] Loud Cicada

!?蝉?!倍数容斥,不管了非常简单,。恰好转至少,直接跑就是了。我觉得这个也可以生成函数跑,但是貌似有点大炮打蚊子了 /kk。

感觉本质和 P9489 ZHY 的表示法相同,但是两者在答案统计上有一些区别。说的道理。

[ABC309G] Ban Permutation

感觉见过,但没写。直接 DP,然后发现会有重复计数,跑容斥。注意到 \(x\) 非常小,那么直接对这个集合状压 DP,直接暴力转移就是对的。

P3175 [HAOI2015] 按位或

Min-Max 容斥 + SOS DP,非常典和简单。

https://www.luogu.com.cn/article/2iyfr7kj

P3349 [ZJOI2016] 小星星

感觉在学生成函数的时候把这个题咕了,就是标号树计数问题。而不是这样的,好像之前做过,见下。直接状压 DP,然后 sos dp 稍微优化一下即可。之前好像写过子集枚举的意义,但是没找到。

https://www.luogu.com.cn/article/2ivb5hso

CF1874E Jellyfish and Hack

模拟赛题,没改我是区。直接设 DP,然后进行滚木优化。感觉很难啊。!?多项式 Trick?!用这个东西来降幂,系数转点值。

[AGC064D] Red and Blue Chips

本来的模拟赛 T4?非常标准的组合建模题。

哈集幂级数

集合划分容斥。

P6846 [CEOI 2019] Amusement Park

无向图无环方案数,\(n\) 很小。本质是 DAG 的定向操作,图计数问题。对于 DAG,枚举 \(0\) 度点删除。

P11714 [清华集训 2014] 主旋律

强连通概率。关键在于刻画强连通。缩点后就会变成 DAG 的计数问题,只是点变成点集,多了一层容斥。


https://www.luogu.com.cn/article/4ab7q8v0