CF1821F 题解

lcjqwq · 2023-04-22 15:23:48 · 题解

解法1：

对于一个状态考虑贪心，能往左就往左倒，否则往右倒。 设 f_{i,j} 表示考虑了前 i 颗树最后倒在 j 的方案数。

考虑往一个位置 j 后面加一颗新的树转移：

• 2 f_{i,j} \to f_{i+1,l}$ 当 $l\in{[j+k+1,j+2k]}
• f_{i,j} \to f_{i+1,l}$ 当 $l\in{[j+2k+1,\inf]}

写成生成函数的形式后，答案可以表示为 \sum\limits_{t=0}^{n}([x^t](\sum\limits_{i=k+1}^{2k}2x^i+\sum\limits_{i=2k+1}^{\inf} x^i)^m)。

直接使用多项式快速幂可以做到 O(n \log n) 的时间复杂度。

考虑继续推导：

设：

• f(t)=[x^{tk}](2-x^k)^m=(-1)^t2^{m-t}\binom{m}{t}
• g(t)=[x^t](\frac{1}{1-x})^{m}=\binom{t+m-1}{m-1}

设 h(n)=\sum\limits_{i=0}^{n} g(i)，那么答案为 \sum\limits_{ki+j\leq n-m(k+1)}f(i)g(j)=\sum\limits_{0 \leq i \leq m} f(i) h(n-m(k+1)-ki)。代入计算即可。时间复杂度 O(n)。

解法2：

我们考虑设 p_i 为考虑前 i 颗树都倒下后最后一个位置（也就是 dp 中的转移点）。那么根据上述 dp 转移，对于任意的 i，都有 p_i-p_{i-1} \ge k+1 。并且如果同时满足 p_i-p_{i-1} \leq 2k，那么会对答案造成一个 2 的贡献。

考虑把前 m 段中都去掉必须有的 k+1 个位置，那么我们把问题转化为：在一个长度为 n-m(k+1) 序列里放 m 个不降的 p_i 并将序列划分成 m+1 个区间 (p_{i-1},p_i](1\leq i \leq m+1,0=p_0\leq p_1 \cdots \leq p_{m+1}=n)。

在前 m 个区间中（不算第 m+1 个区间），每当有一个长度 \leq k-1 的区间，贡献就会乘以 2。我们要求出所有方案的贡献之和。

设 f_x 表示前 m 个区间中恰好有 x 个区间长度 \ge k，g_x 表示钦定其中 x 个区间长度 \ge k。

我们可以得到：

• g_x=\binom{m}{x}\binom{n-m(k+1)-xk+m}{m}
• g_x=\sum\limits_{i=x}^{m} \binom{i}{x}f_i
• 答案为 \sum\limits_{i=0}^{m} 2^{m-i} f_i

由二项式反演可以得到 f_x=\sum\limits_{i=x}^{m} (-1)^{i-x}\binom{i}{x} g_i 。

于是有：

直接 O(n) 计算即可。

解法3：

事实上，这个 dp 有另一种转移方式：考虑一个一个位置的枚举：

此时我们可以考虑这个 dp 的组合意义，相当于最初在 (0,0)，我们要走到 (m,n)，每次可以选择加上向量 (0,1)，贡献为 1；选择 (1,k+1)，贡献为 2；选择 (1,2k+1)，贡献为 -1。

可以发现，第二种转移和第三种转移的总数为 m，我们直接枚举走了 t 个第三种转移，可以计算出此时有 m-t 个第二种转移以及 n-(m-t)(k+1)-t(2k+1) 个第一种转移。

将第二和第三种转移排列好有 \binom{m}{t} 种方案，使用插板法计算出把第一种转移插入到第二三种转移的空隙中的方案数，最后可以得到答案为：

可以发现三种做法殊途同归，同样 O(n) 计算即可。

代码：https://www.luogu.com.cn/paste/8vgbd3uy