HDU 5730 Shell Necklace (dp,cdq分治,FFT | NTT)

给出n长度的项链,不同的分割方案可以得到不同的价值,价值=a[l1] * a[l2] * … * a[lk],l表示分割的长度。

那么一个很显然的dp,dp[i] = sigma{ dp[i – j] * a[j] | 1 <= j < i }
直接求是O(n ^ 2),但是这是一个卷积的形式,所以可以用cdq分治+FFT或者NTT搞。

FFT:

 

NTT:

 

LEAVE A COMMENT