【题单】计数专题

https://cplusoj.com/d/senior/contest/69c9f3a81363e1a076a427a9

AT_arc101_c [ARC101E] Ribbons on Tree

容斥每条边是否被覆盖，一个连通块大小为 \(s\)，则连边方案数是 \(\prod_{i=1}^{s/2} (2i-1)\)。

Topcoder13444 CountTables

以下的所有方案数都要求每列不相等。
设 dp \(f_i\) 表示现在已经考虑了前 \(i\) 行，现在我们用 \((c^i)^{\underline m}\) 减去不合法的方案数。用第二类斯特林数把每行分到 \(j\) 个相同的集合中，递归 \(f_j\)。

AT_arc062_d [ARC062F] AtCoDeerくんとグラフ色塗り

显然能转的环都在一个点双里面，那么跑一下圆方树，对于环或者边的情况，就是 burnside。否则每种置换都能造出来，那么就是一个组合数。

考虑一个 \(\deg_u\ge 3\) 的点，连接到 \(u\) 的两条边是可以交换的。然后我们可以把任意两条边都放到这上边，然后就做完了。

BZOJ1478 Sgu282 Isomorphism

P4128 [SHOI2006] 有色图
枚举所有的置换 \(p\)，那么考虑每个置换环之间的连边，形成多少个等价类。

BZOJ1547 周末晚会

Burnside 一下，那么就是每次给定 \(n\)，求 \(n\) 点的环有多少种染色方法使得不存在 \(k\) 个黑点紧挨着。
对于 \(k\ge N\) 的情况我们可以特判，那么环上至少有一个白点。
先规定第一个点是白点，那么该白点后面紧挨着的黑点都可以作为开头。\(O(n)\) 递推即可。

AT_agc022_f [AGC022F] Checkers

\(A\) 跳过 \(B\)，贡献是 \(2B-A\)。连边 \(B\to A\)，构成一棵树。
要确定最后点的坐标，只需要关注：

• 每个点与父亲正负号是否相同。
• 每个点的深度。

一个节点 \(u\) 的儿子中有 \(\left\lfloor\frac{son_u}{2}\right\rfloor\) 个在 \(u\) 处被取反偶数次。
那么从浅往深 dp，设 \(f_{i,j}\) 表示当前有 \(i\) 个节点，钦定当前最后一层节点有 \(j\) 个是有奇数个儿子。
现在添加一层 \(k\) 个节点到树中，那么在父亲处，被取反次数奇偶性与父亲相同的节点有 \(\frac{k-j}{2}\) 个。
然后我们需要钦定这层节点中的 \(l\) 个，他们与父亲符号相同。要想做到这点我们要有 \(|l-\frac{k-j}{2}|\) 个有奇数儿子的节点。如果多选择偶数个有奇数儿子的节点会导致算重。
那么总复杂度 \(O(n^4)\)。

hdu4372 Count the Buildings

P4609 [FJOI2016] 建筑师
考虑按照 n 分成两边，将前缀/后缀最大值和他后面跟着的数分成一组，那么就可以用斯特林数划分圆排列，将每个排列内最大值作为第一个。最后用组合数分配组到 \(n\) 左/右边即可。