伐木题解

思路

把树的位置从左到右排列，并固定每棵树的倒向。相邻两棵树的覆盖区间必须严格分离，最左和最右的覆盖区间还不能越过边界。直接枚举位置集合与倒向可以解决极小规模；当只有一棵树时，也可以直接计算允许位置的并集。

满分做法使用容斥。先暂时忽略若干个“左右两种倒法都会与相邻结构产生冲突”的禁制，把每棵树及其倒向造成的必需间隔压缩掉。固定容斥参数 $i$ 后，需要安排的剩余空位可以用插板法计数。

做法

预处理阶乘与逆阶乘，以便在常数时间内计算组合数。约定当 $a<b$ 或 $a<0$ 时，$\binom ab=0$。

令 $i$ 从 $m$ 递减到 $0$。选择 $i$ 个被容斥标记的树有 $\binom mi$ 种方式；未被标记的倒向贡献系数 $2^{m-i}$。压缩所有树和必需间隔后，插板法给出的方案数为

$$\binom{n-k(m+i)}m.$$

因此答案为

$$\sum_{i=0}^{m}(-1)^i 2^{m-i}\binom mi\binom{n-k(m+i)}m.$$

所有运算均在模 $998\,244\,353$ 下进行。组合数上标不会超过 $n$，预处理到 $n$ 即可。

对于 $n\le18$ 的子任务，可以枚举所有恰含 $m$ 个位置的集合。按位置从左到右扫描，维护此前覆盖区间能够达到的最小右端点；对当前树尝试合法的左倒与右倒，保留新的最小右端点。若扫描结束仍可达，则该位置集合合法。

当 $m=1$ 时，向右倒允许位置 $[1,n-k]$，向左倒允许位置 $[k+1,n]$，直接求两个区间的并集大小。

正确性证明

对固定的位置集合，极小规模扫描始终保留最小可达右端点。若两种倒法都可行，较小的右端点不会减少后续树的选择，因此该状态支配所有更大的右端点。归纳可知扫描判定与“存在一组合法倒向”等价。

在满分计数中，固定 $i$ 个容斥标记后，每棵树与相邻树之间必须预留的长度均已被压缩。压缩后剩余的 $m$ 棵树等价于在 $n-k(m+i)$ 个位置中选择 $m$ 个有序位置，方案数为 $\binom{n-k(m+i)}m$。选择标记集合贡献 $\binom mi$，未标记树的自由倒向贡献 $2^{m-i}$。按容斥原理，含奇数个标记的项应减去，含偶数个标记的项应加上，于是得到上述求和式。该式恰好计算所有至少存在一种合法倒向的位置集合，并且每个位置集合最终被计数一次。

复杂度

预处理和求和的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$。