Description：

题意：给出 $n,b,c,d,f(x)=\sum^{n−1}_{i=0}a_ix_i$ ，求 $f(b\times c^{2k}+d):0≤k<n$ ，取模 $10^6+3$ 。

$1\leqslant n\leqslant10^5$

## Solution：

先暴力代式子： $$ \begin{align} ans[k]&=f(b\times c^{2k}+d)\\ &=\sum_{i=0}^{n-1}a_i(b\times c^{2k}+d)^i\\ &=\sum_{i=0}^{n-1}a_i\sum_{j=0}^i\binom ijb^jc^{2kj}d^{i-j}\\ &=\sum_{i=0}^{n-1}a_ii!\sum_{j=0}^i\frac{b^jc^{2kj}}{j!}\frac{d^{i-j}}{(i-j)!}\\ &=\sum_{j=0}^{n-1}\frac{b^jc^{2kj}}{j!}\sum_{i=j}^{n-1}a_ii!\frac{d^{i-j}}{(i-j)!}\\ \end{align} $$ 设 $r[i]=a_{n-1-i}(n-1-i)!,p[i]=\frac{d^i}{i!}$ ，那么： $$ \begin{align} &\sum_{i=j}^{n-1}a_ii!\frac{d^{i-j}}{(i-j)!}\\ =&\sum_{i=j}^{n-1}r[n-1-i]p[i-j]\\ =&\sum_{i=0}^{n-1-j}r[i][n-1-j-i] \end{align} $$ 于是后面是个卷积，设为 $f[j]$ ，那我们就是要求： $$ ans[k]=\sum_{j=0}^{n-1}\frac{b^jc^{2kj}f[j]}{j!} $$ 不是一个卷积，看上去非常不好求，但是我们可以利用： $(k-j)^2=k^2+j^2-2kj$ 的方法把 $c$ 的幂展开： $$ ans[k]=\sum_{j=0}^{n-1}\frac{b^jc^{2kj}f[j]}{j!}=c^{k^2}\sum_{j=0}^{n-1}\frac{b^jc^{j^2}f[j]}{j!c^{(k-j)^2}} $$ 于是就是一个卷积了。

注意 $k-j$ 可能为负因此要先乘上 $x^n$ 。

Code：

代码就不写了