考虑如何判断一个方案是合法的，很容易想到贪心，从左到右考虑第 \(i\) 棵树：
- 如果这棵树能向左倒即 \([x_i-k,x_i]\) 没有被占据，就向左倒。
- 否则向右倒。
显然向左倒对之前已经倒下的树没有影响，而对后面的树来讲，这棵树向左倒能留下尽量多的空间，所以优先向左倒一定不劣。
所以考虑一个 dp，设 \(f_{i,j}\) 为第 \(i\) 棵树倒下后最右覆盖到 \(j\) 点的方案树，考虑新增一棵树：
- 对于 \(p\in [j+k+1,j+2k]\) 的位置，它有两种方式被覆盖到（把树放到 \(p\) 然后向左倒、把树放到 \(p-k\) 然后向右倒），于是 \(2f_{i,j}\to f_{i+1,p}\)。
- 对于 \(p\in [j+2k+1,+∞)\) 的位置，它只有一种方式被覆盖到（时刻保证贪心方案的性质），\(f_{i,j}\to f_{i+1,p}\)。
最后枚举 \(j\) 的位置对 \(f_{n,j}\) 求和即可。那么就可以写成 GF 的形式：
\[\sum\limits_{i=1}^n[x^i]\left(\sum\limits_{j=k+1}^{2k}2x^j+\sum\limits_{j=2k+1}x^j\right)^m \]这是多项式快速幂，但我不会。
考虑写成封闭形式：
\[\begin{aligned}&\sum\limits_{j=k+1}^{2k}2x^j+\sum\limits_{j=2k+1}x^j\\=&\sum\limits_{j=k+1}x^j+\sum\limits_{j=k+1}^{2k}x^j\\=&\frac{x^{k+1}}{1-x}+\frac{x^{k+1}(1-x^k)}{1-x}\\=&x^{k+1}\cdot\frac{2-x^k}{1-x}\end{aligned} \]所以：
\[\begin{aligned}&\sum\limits_{i=1}^n[x^i]\left(\sum\limits_{j=k+1}^{2k}2x^j+\sum\limits_{j=2k+1}x^j\right)^m\\=&\sum\limits_{i=0}^{n-m(k+1)}[x^i]\left(\frac{2-x^k}{1-x}\right)^m\end{aligned} \]考虑到 \((2-x^i)^m\) 中 \(x\) 的次数始终为 \(k\) 的倍数，令 \(f(i)=[x^{ik}](2-x^k)^m\)，令 \(g(i)=[x^i](1-x)^{-m}\)：
\[\begin{aligned}f(i)=&[x^{ik}](2-x^k)^m\\=&[x^i](2-x)^m\\=&2^{m-i}(-1)^i\dbinom{m}{i}\\g(i)=&[x^i](1-x)^{-m}\\=&\dbinom{m+i-1}{i}\end{aligned} \]那么即求 \(\sum\limits_{ik+j\le n-m(k+1)}f(i)g(j)\)，预处理 \(g\) 的前缀和，然后求 \(\sum\limits_{ik+j= n-m(k+1)}f(i)S_g(j)\) 即可。
很好写。
标签：frac,limits,sum,ik,Timber,CF1821F,aligned,2k From： https://www.cnblogs.com/Ender32k/p/17569337.html