2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅
网络赛最难的一个题，也是我唯一一个不会做的。
看了大大的题解发现我其实已经推到了倒数第二步T_T
但是眼拙没看出来可以写成卷积形式。。。所以按照那个推法无论如何都是O(n^2)的复杂度，变成卷积形式就可以用fft加速直接O(nlogn)一次性求出所有点的值了。。。
继续阅读“[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅”
网络赛最难的一个题，也是我唯一一个不会做的。
看了大大的题解发现我其实已经推到了倒数第二步T_T
但是眼拙没看出来可以写成卷积形式。。。所以按照那个推法无论如何都是O(n^2)的复杂度，变成卷积形式就可以用fft加速直接O(nlogn)一次性求出所有点的值了。。。
继续阅读“[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅”