hdu6061

acm hdu

记$r=-\sum a_i$

问题相当于展开$f(x+r)$。
我们可以把每一项用二项式定理展开，然后可以发现这是可以用$FFT$优化的。

时间复杂度：$O(n\log{n})$

• 记 $f(x) = a_0x^0 + a_1x^1 + a_2x^2 + \cdots a_nx^n$
• 则 $f(x+r) = a_0(x+r)^0 + a_1(x+r)^1 + a_2(x+r)^2 + \cdots a_n(x+r)^n$
• 考虑把每一项用二项式定理展开，则有：
  
  • $x_0$的系数为：$a_{0}C_{0}^{0}r^{0} + a_{1}C_{1}^{1}r^{1} + a_{2}C_{2}^{2}r^{2} + a_{3}C_{3}^{3}r^{3} + \cdots + a_nC_{n}^{n}r^n$
  • $x_1$的系数为：$a_{1}C_{1}^{0}r^{0} + a_{2}C_{2}^{1}r^{1} + a_{3}C_{3}^{2}r^{2} + a_{4}C_{4}^{3}r^{3} + \cdots + a_nC_{n}^{n-1}r^{n-1}$
  • $\cdots$
• 把组合数展开之后可以发现：
  
  • $x_0$的系数为：$a_{0} \frac{0!}{0!0!} r^{0} + a_{1} \frac{1!}{0!1!} r^{1} + a_{2} \frac{2!}{0!2!} r^{2} + a_{3} \frac{3!}{0!3!} r^{3} + \cdots + a_n \frac{n!}{0!n!} r^n$
  • $x_1$的系数为：$a_{1} \frac{1!}{1!0!} r^{0} + a_{2} \frac{2!}{1!1!} r^{1} + a_{3} \frac{3!}{1!2!} r^{2} + a_{4} \frac{4!}{1!3!} r^{3} + \cdots + a_n \frac{n!}{1!(n-1)!} r^{n-1}$
  • $\cdots$
• 提取一下公因式，有：
  
  • $x_0$的系数为：$\frac{1}{0!}(a_{0} \frac{0!}{0!} r^{0} + a_{1} \frac{1!}{1!} r^{1} + a_{2} \frac{2!}{2!} r^{2} + a_{3} \frac{3!}{3!} r^{3} + \cdots + a_n \frac{n!}{n!} r^n)$
  • $x_1$的系数为：$\frac{1}{1!}(a_{1} \frac{1!}{0!} r^{0} + a_{2} \frac{2!}{1!} r^{1} + a_{3} \frac{3!}{2!} r^{2} + a_{4} \frac{4!}{3!} r^{3} + \cdots + a_n \frac{n!}{(n-1)!} r^{n-1})$
  • $\cdots$
• 然后你就发现括号里的这些系数其实就是卷积，可以用$FFT/NTT$优化。
• $FFT$的两个函数可以为：
  $$A(x) = a_{0}0!x^0 + a_{1}1!x^1 + a_{2}2!x^2 + a_{3}3!x^3 + \cdots + a_{n}n!x^n\\ B(x) = \frac{r^0}{0!}x^{n} + \frac{r^1}{1!}x^{n-1} + \frac{r^2}{2!}x^{n-2} + \frac{r^3}{3!}x^{n-3} + \cdots + \frac{r^n}{n!}x^0$$
• 最后得到的函数的$x^n, \ldots, x^{2n}$项的系数除以$\frac{1}{i!}$即为答案