题意：
在 \([1, n]\) 的区间里放 \(m\) 棵树，每棵树的高度为 \(k\)。求有多少种放置树的方法，满足：
- 每个树都在整点上，且每个点最多只能放一棵树。
- 存在一种砍倒树的方案，使得树倒了之后不会越界，也不会有某个点被超过一棵树占据。你可以自由选择树向左倒（也就是占据区间 \([x - k, x]\)）或者向右倒（也就是占据区间 \([x, x + k]\)）。
\(n, m, k \le 3 \times 10^5\)
思路：
先让 \(k = k + 1\)，这样就是覆盖点了。
首先，我们考虑一个判定行的算法：从左往右扫，能往左倒就往左倒，否则往右倒。
基于这个，我们可以设计 \(dp\) 方程，设 \(f_{n, m}\) 表示当前种了 \(m\) 棵树，最右边倒下的位置是 \(n\)。
我们可以得出方程：
\[f_{n, m} = \sum_{i=0}^{m - k}f_{i, m - 1} + \sum_{i = m - 2k + 2}^{m - k}f_{i, m - 1} \]考虑生成函数优化，设 \(F_m(x) = \sum_{n}f_{n,m}x^n\)，则我们可以通过上面的式子得到：
\[F_m(x) = F_{m-1}(x)(\sum_{i=k}^{\infty}x^i + \sum_{i = k}^{2k - 2}x^{i}) \]化简一下得到：
\[F_m(x) = F_{m-1}(x)\frac{2x^{k} - x^{2k - 1}}{1 - x} \]由于 \(F_0(x) = 1\)，所以：
\[F_m(x) = (\frac{2x^{k} - x^{2k - 1}}{1 - x})^m \]将分子展开得到：
\[x^{km}\sum_{i=0}^m\binom{m}{i}2^{m-i}(-1)^ix^{(k-1)i} \]将分母根据 \(\frac{1}{(1-x)^n} = \sum_i \binom{n + i - 1}{n - 1}x^i\) 展开得到：
\[\sum_{j=0}^{\infty}\binom{m + j - 1}{m - 1}x^j \]现在我们要求出所有小于等于 \(n\) 次的项的系数和，考虑枚举 \(i\)，得到：
\[\sum_{i = 0}^m\binom{m}{i}2^{m-i}(-1)^i\sum_{j \le n - km - (k - 1)i}\binom{m + j - 1}{m - 1} \]后面的和式可以进一步化简，我们其实就是要计算：
\[\sum_{i=0}^t \binom{m + i}{m} \]的和。
考虑直接暴力拆开组合数得到：
\[\frac{\sum_{i=0}^t(m+i)^{\underline{m}}}{m!} \]而根据离散微积分的积分：
\[\sum_{a}^bx^{\underline{m}}\Delta x = \frac{1}{m+1}x^{\underline{m+1}}\mid^a_b \]我们可以对分母计算得到：
\[\frac{\frac{1}{m+1}(m + t + 1)^{\underline{m+1}} - \frac{1}{m + 1}m^{\underline{m+1}}}{m!} \]发现后面的那一项会变成 \(0\)，所以得到：
\[\frac{(m+t + 1)^{\underline{m+1}}}{(m+1)!} \]也就是：
\[\binom{m + t + 1}{m + 1} \]代入到答案中就能得到：
\[\sum_{i = 0}^m\binom{m}{i}2^{m-i}(-1)^i\binom{n - km - (k - 1)i + m}{m} \]然后 \(O(n)\) 计算即可。
标签：frac,题解,sum,得到,CF1821F,binom,2k,underline,Timber From： https://www.cnblogs.com/rlc202204/p/18213926