CF1821F Timber 题解

· · 题解

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

暴力转移可以得到 \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