专门放一些不大可能会考的计数题，长期更新。 大约是输入的只有问题规模，输出的只有相应方案数。 luogu6561 [SBCOI2020] 人 两两不相邻这个条件不是很容易搞。 考虑把 $[1,2m]$ 分成 $m$ 个数对，形如 $(\text{odd},\text{even})$，其中 $\text{odd} +1 =\text{even} $ …

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 $\texttt{Observation}$ ${a_i}$ 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 ${a_i}$ 划分成若干个集合，满足其中两两乘积为完全平方数。 $\texttt{proof}$ 考虑和 $a_i$ 相乘为完全平方数的数集 ${a_…

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…