Tips

仅含题解,代码详见github喜欢的话点个star

1003. Kanade’s sum

1005. RXD and dividing

1006. RXD and functions

易得,$g_m(x)=f(x-\sum a_i)$ 。

记 $S=\sum a_i $,代入:

$$\large \begin{equation}\begin{split}
g_m(x)&=\sum_{i=0}^{n}c_i(x-S)^i \\
&=\sum_{i=0}^{n}c_i\sum_{j=0}^{i}C_{i}^{j}x^j(-S)^{i-j} \\
&=x^0\sum_{j=0}^{n}c_jC_{j}^{0}(-S)^{j-0}+\cdots+x^n\sum_{j=0}^{n}c_jC_{j}^{n}(-S)^{j-n} \\
&=\sum_{i=0}^{n}x^i\sum_{j=0}^{n}c_jC_{j}^{i}(-S)^{j-i} \\
&=\sum_{i=0}^{n}x^i\sum_{j=i}^{n}c_j\cfrac{j!}{i!\cdot (j-i)!}(-S)^{j-i}
\end{split}\end{equation}$$
$\large \therefore b_i=\cfrac{1}{i!}\sum_{j=i}^{n}j!c_j\cdot \cfrac{(-S)^{j-i}}{(j-i)!}$
记$\large A_i=i!c_i,B_i=i!b_i,d_i=A_{n-i},e_i=\cfrac{(-S)^{i}}{i!},(1\le i\le n)$
$\large B_i=\sum_{k=i}^{n}A_k\cdot e_{k-i}=\sum_{k=0}^{n-i}d_{n-i-k}e_{k}$

考虑多项式乘法:
$A(x) = \sum_{i=0}^{n}a_ix^{i}$
$B(x) = \sum_{i=0}^{n}b_ix^{i}$
$C(x) = A(x)B(x) = \sum_{i=0}^{2n}c_ix^{i}$
$c_j = \sum_{i=0}^{j}a_ib_{j-i}$,

所以$B_i$即为多项式$D(x)E(x)$第$n-i$项的系数。

由于题目是在模意义下的,所以要用NTT,且费马质数必须为所给的模数。

1011. RXD’s date