hdu5730 分治fft
题意:$dp[n]=\sum_{i=1}^ndp[i]*a[n-i]+a[n]$,求dp[n],
题解:分治fft裸题,就是用cdq分治加速fft,因为后面的需要用到前面的dp来算,不可能每次都fft过去,那样复杂度就$O(n^2\logn)$了
考虑当前枚举到[l,r]区间,左侧是[l,m]对于右侧每一个dp[x],左侧的贡献有$\sum_{i=l}^m dp[i]*a[x-i]$,那么我们需要快速算出左侧所有dp对右侧每个dp的所有贡献
$x_0|x_1|x_2|...|x_{m-l}$
$dp_l|dp_{l+1}|dp_{l+2}|...|dp_{m}$
$y_0|y_1|y_2|...|y_{r-l}$
$a_1|a_2|a_3|...|a_{r-1}$
那么卷积之后就变成了系数就变成
$m-l|m-l+1|...|r-l-1|$
挨个加到对应的dp{m+1->r}里去即可
需要注意的是cdq时每次一定是先把左侧算完,再算右边,(以前的cdq是先算底层,从叶到根,因为要做归并操作),这里是因为对于更新dp[x]的dp[i],dp[i]必须要更新完才能更新dp[x],
点赞 (0)
回复