CF1251F Red-White Fence
题解：发现红色的板子很少，枚举每一个红板子分别做，对于只有一个不重复的合法白板子，记总共有(c1)个，那么得到宽度为(k)的先上升后下降序列有(2^{k}inom{c_1}{k})，而对于出现重复超过2个的白板子，都可看作只出现了2次，记总共有(c2)个，那么得到宽度为(k)的先上升后下降序列有(inom{2c_2}{k})，答案数列就是(sum_{i=0}^{n}2^{i}inom{c_1}{i})和(sum_{i=0}^{n}inom{2c_2}{i})的卷积后多项式的系数。复杂度(O(nlogn))
代码
付公主的背包
题解：对于每一个物品都有无限个，假设一个物品的体积为(V)，其对应的生成函数为(frac{1}{1-z^V})，那么答案数列的生成函数就是(prodfrac{1}{1-z^V})。可以先考虑分母里的式子，再最后多项式求逆回去。发现如果直接做复杂度很高，可以将乘法通过(e)转化为加法，问题是如何快速计算(ln(1-z^V))的值。设(F(z)=1-z^V)
[G(z)=lnF(z)
]
[G'(z)=frac{F'(z)}{F(z)}
]
[G'(z)=frac{-Vz^{V-1}}{1-z^V}
]
[G'(z)=-sum_{i>=0}Vz^{V-1+Vi}
]
[G(z)=-sum_{i>=0}frac{Vz^{V+Vi}}{V+Vi}
]
[G(z)=-sum_{i>=1}frac{z^{Vi}}{i}
]
推到这里，我们可以枚举每一个物品，在(O(nlogn))的时间里算出(prod G(z))的系数，再做一次(EXP)，最后多项式求逆回去就是答案。注意要将重复的物品用桶记下来一起做。
代码