取整函数的性质

\(n\) 是整数，\(a\) 是正整数，\(0 < \varepsilon < 1/a\)，则

• \(\ceil{n/a - \varepsilon} = \ceil{n/a}\)
• \(\ceil{n/a + \varepsilon} = \ceil{(n+1)/a}\)
• \(\floor{n/a + \varepsilon} = \floor{n/a}\)
• \(\floor{n/a - \varepsilon} = \floor{(n - 1) / a}\)

对任意整数 \(n\) 和任意正整数 \(a, b\) 都有

• \(\ceil{\ceil{n/a}/b} = \ceil{n /(ab)}\)
• \(\floor{\floor{n/a} / b} = \floor{n/(ab)}\)

证明：若 \(a\) 能整除 \(n\) 结论显然成立。假设 \(a\) 不能整除 \(n\)，则 \(n\) 可表为 \(qa + r\)，其中 \(1 \le r < a\)。可知 \(\ceil{n / a} = q+1\)，左边等于 \(\ceil{(q+1)/b}\)。右边等于 \(\ceil{(qa + r) /(ab)} = \ceil{q/b + r/(ab)}\)。\(r/(ab) < 1/b\)，所以 \(\ceil{q/b + r/(ab)} = \ceil{(q+ 1) /b}\)。同理可证第二个等式。

Bonus question

在 \(O(N(\log N)^2)\) 时间内计算多项式乘积 \(\prod_{1 \le i \le N} (A_i x + 1)\)。

做法：弄一个队列。最初把乘积的每一项 \((A_i x + 1)\) 都放到队列里。然后不断从队首取出两项相乘，把乘积从队尾加进队列；直到队列里只剩一个多项式，就是结果。

下面来证明这个做法的时间复杂度是 \(O(N (\log N)^2)\)。

考虑数列 \(N_0 = N, N_1 = \ceil{N/2}, N_2 = \ceil{N_1 / 2}, N_3 = \ceil{N_2 / 2}, \dots, N_K = 1\)。

根据取整函数的性质，有 \(N_i = \ceil{N/2^i}\)。从而知 \(K = \ceil{\log N}\)。

第一轮是不超过 \(N_1\) 对次数不超过 \(1\) 的多项式相乘，第二轮是不超过 \(N_2\) 对次数不超过 \(2\) 的多项式相乘，第三轮是不超过 \(N_3\) 对次数不超过 \(4\) 的多项式相乘，以此类推。

我们知道 FFT 算法可以在 \(O(n \log n)\) 的时间内算出两个次数不超过 \(n\) 的多项式的乘积。

因此上述算法的时间复杂度可表为 \[\begin{equation} \sum_{1 \le i \le K} \ceil{N/2^i} 2^{i - 1}(i - 1) \label{1} \end{equation}\]

\(\eqref{1} < \sum_{1 \le i \le K} (N/2^i + 1) 2^ii < N(1 + K)K + K 2^{K + 1} = O(N(\log N)^2)\)。