hdu7381 Cargo
式子部分由 liuhangxin 想出。
\[\sum\limits_{i = 0}^{n}\binom{k}{i}(n - i)^{k - i}[x^i]\prod\limits_{id = 1}^{m}(1 - x^{c_{id}}) \]实现部分当时胡了一个分治 NTT，也不知道时间复杂度为什么是对的，但是过了。
AC 后十多分钟分析出来这个做法的时间复杂度为 \(O(n\log{m}\log{n})\)。
考虑两个长为 \(w_1\) 和 \(w_2\) 的多项式自叶向根合并，本层运算消耗时间 \(O(w_1\log{w_1} + w_2\log{w_2})\)。
合并到上一层，得到长为 \(w_1 + w_2\) 的多项式，这个多项式在它那一层的运算消耗时间 \(O((w_1 + w_2)\log({w_1 + w_2}))\)。
把 \(\log{x}\) 放大成 \(\log{n}\)，\((w_1 + w_2)\log{n}\) 可以拆成 $w_1\log{n} + w_2\log{n} $。
对 \(w_i\log{n}\) 进行统计，由于采用分治，向上最多被计入 \(\log{m}\) 次，又因为 \(\sum{w} = n\)，故总时间复杂度为 \(O(n\log{n}\log{n})\)。
标签：log,多项式,复杂度,分治,NTT,上辈子,id From： https://www.cnblogs.com/Schucking-Sattin/p/17994966