【HDU6061】RXD and functions


题意

定义\(g_i(x)=g_{i-1}(x-a_i)\),给定所有的\(a_i\)以及\(g_0\),求\(g_m\)。

分析

显然\(g_m(x)=g_{m-1}(x-a_m)=\cdots =g_{0}(x-\sum _{i=0}^{m} a_i)\)。

我们设\(a=\sum _{i=0}^{m} a_i\),那么就有

$$g_m(x)=g_0(x-a)=\sum _{i=0}^{n}c_i(x-a)^i$$

$$=\sum _{i=0}^{n} c_i \sum_{j=0}^{i} C_{i}^{j} x^j (-a)^{i-j}$$

$$=\sum_{j=0}^{n} \sum _{i=j}^{n} c_i C_{i}^{j} x^j (-a)^{i-j}$$

$$=\sum_{j=0}^{n} \sum _{i=0}^{n-j} c_{i+j} C_{i+j}^{j} x^j (-a)^{i}$$

$$=\sum_{j=0}^{n} \sum _{i=0}^{n-j} c_{i+j} \frac{(i+j)!}{j!i!} x^j (-a)^{i}$$

如果我们令\(A_i=c_{n-i}(n-i)!\),\(B_i=\frac {(-a)^i}{i!}\)

那么有 原式\(=\sum_{j=0}^{n} A_{n-j-i} B_i j! x^j\)

也就是得到了\(x^j\)的系数。

\(A_{n-j-i}\times B_i\)是一个卷积形式,利用 NTT 计算即可。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 2,002

Categories

Archive