本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-16 10:18:03

:::::info[闲话] 计数题怎么这么难。
::::: :::::info[题目基本信息] 考察：组合数学，动态规划 DP，数学（$2600$）。
题目简介：
在一个数轴上，有 $1$ 到 $n$ 的 $n$ 个位置，现在你要在 $m$ 个位置种上树并将他们砍倒，砍倒后的树可以钦定他们向左倒或向右倒，给定常数 $k$，若该树位置为 $x$，则向左倒会覆盖 $[x-k,x]$ 的所有位置，向右倒会覆盖 $[x,x+k]$ 的所有位置，问有多少种不同的种树方案使得他们能在砍倒后满足一个位置不被覆盖两次（对 $998244353$ 取模），方案不同当且仅当存在一个位置一种方案里种了树而另一种方案没有。
数据范围：

• $1\le m,k\le n\le 3\times 10^5$ ::::: 先考虑如何决策这些树是如何倒下的，这就是一个经典贪心，优先让每个树向左倒，倒不下在向右倒。
  那么我们考虑朴素 DP，设 $dp_{i,j}$ 表示种了前 $i$ 棵树，最后一棵树最后覆盖的位置为 $j$，初始时 $dp_{0,0}=0$。
  那么容易得到转移（对于 $dp_{i,j}$ 向后转移的过程）：
• $\forall j_2\in[j+k+1,j+2k],dp_{i+1,j_2}\leftarrow 2dp_{i,j}$，即既能向左倒又能向右倒。
• $\forall j_2\in[j+2k+1,+\infty),dp_{i+1,j_2}\leftarrow dp_{i,j}$，即只能向左倒。

暴力转移可以得到 $\Theta(n^2m)$ 做法，利用数据结构优化可以得到 $\Theta(nm\log n)$ 做法，然后就没有出路了。

我们考虑使用一些组合数学知识，设 $\{p_m\}$ 表示在种树的过程中，每前 $i$ 棵树时最后一棵树的最后覆盖位置构成的序列，同时令 $p_0=0$，那么由上面的转移方程可以得到 $\forall i\in[1,m],p_i-p_{i-1}\ge k+1$，同时当 $p_i-p_{i-1}\le 2k$ 时会有 $2$ 的贡献，那么我们可以先在 $n-m(k+1)$ 个位置里选 $m$ 个不降的位置，然后在他们前面分别补 $k+1$ 个位置，这样我们就消去了 $p_i-p_{i-1}\ge k+1$ 的限制条件，贡献条件 $p_i-p_{i-1}\le 2k$ 转变成 $p_i-p_{i-1}\le k-1$。
现在我们考虑设 $f_i$ 表示这 $m$ 个位置里面恰好有 $i$ 个满足 $p_i-p_{i-1}\ge k$ 的位置的选择方案数，但是这个东西并不好直接求，所以我们考虑再设 $g_i$ 表示这 $m$ 个位置里面钦定其中 $i$ 个满足 $p_i-p_{i-1}\ge k$ 的位置的选择及钦定方案数，这个容易用组合数表示出来，首先钦定会带来 $\dbinom{m}{i}$ 的贡献，然后我们需要在 $n-m(k+1)$ 的序列选出 $m$ 个不降位置，其中一些位置中间需要相隔至少 $k$ 个位置，我们考虑也把这 $k$ 个位置扔掉，变成在 $n-m(k+1)-ik$ 的序列中选出 $m$ 个不降位置，这就是经典插板法，最终会带来 $\dbinom{n-m(k+1)-ik+m}{m}$ 的贡献。
综上我们得到：
$$g_i=\binom{m}{i}\binom{n-m(k+1)-ik+m}{m}$$ 同时由于 $f_i$ 和 $g_i$ 的定义的联系，我们得到：
$$g_i=\sum_{j=i}^m\binom{j}{i}f_j$$ 马上可以反演出：
$$f_i=\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}g_j$$ 由于 $f_i$ 的定义最终答案 $ans$ 为：
$$ans=\sum_{i=0}^m2^{m-i}f_i$$ 把上面的式子堆起来可以得到：
$$\begin{aligned}ans&=\sum_{i=0}^m2^{m-i}\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\&=\sum_{i=0}^m\sum_{j=i}^m2^{m-i}(-1)^{j-i}\binom{j}{i}\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\&=\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j2^{m-i}(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j2^{-i}(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}\sum_{i=0}^j(\frac{1}{2})^i(-1)^{j-i}\binom{j}{i}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-\frac{1}{2})^{j}\&=2^m\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-1)^j2^{-j}\&=\sum_{j=0}^m\binom{m}{j}\binom{n-m(k+1)-jk+m}{m}(-1)^j2^{m-j}\end{aligned}$$ 爽飞了，可以线性计算了。

时空复杂度均为 $\Theta(n+m)$。

code