CF1821F

· · 题解

很适合做 GF 的入门题。

考虑怎么判断一个条件合法，从左往右扫一遍，能往左倒就往左倒即可。

按照这个东西可以设计 dp 状态，设 f_{i,j} 表示前 i 棵树在最优方案下铺到位置 j 的方案数。

考虑转移，分别考虑什么情况往左倒，什么情况从左边往右倒过来即可，有 f_{i,j}=\sum_{l=0}^{j-k-1}f_{i-1,l}+\sum_{l=j-2k}^{j-k-1}f_{i-1,l}。

因为每个 f_i 都是从 f_{i-1} 转移，且形式都很优美，考虑 GF。

令 F_i(x)=\sum_{i\ge 0}f_{i,j}x^j，则所求为 F_m(x) 每一项的系数和，分别考虑两个转移对应的多项式。

左边是 A(x)=\sum_{i\ge k+1}x^i=\frac{x^{k+1}}{1-x}，右边为 B(x)=\sum_{i=k+1}^{2k}x^i=\frac{2^{k+1}-x^{2k+1}}{1-x}。

因为 F_0(x)=1，所以有 F_m(x)=(A(x)+B(x))^m=\frac{(2x^{k+1}-x^{2k+1})^m}{(1-x)^m}。

拆成两个多项式乘起来后，分子可以二项式展开，分母是典中典，那么两个多项式都可以 O(n) 求出。

因为我们不需要知道 F_m(x) 的每一项是多少，只需要知道每一项的和，所以这个也是可以 O(n) 求出的。

总复杂度 O(n)。

https://codeforces.com/contest/1821/submission/202915394