|
|
$f(x)g(x) = \sum_{0\le k \leq m+n} x^k \sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j$ 的 $x^k$ 系数为 $\sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j$
而 $f_i g_j\in\{-1,0,1\}$
所以 $\sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j=\sum_{\substack{0\le i \leq m\\0\le k-i \leq n}}f_i g_j=\sum_{\substack{\max(0,k-n)\le i \leq\min(k,m)}}f_i g_j\le 1+\min(k,m)-\max(0,k-n)$
由此可以得出整个多项式的最大系数的上界
$$\max_{0\le k\le m+n}\left(1+\min(k,m)-\max(0,k-n)\right)$$ |
|
