$\newcommand{ali}[1]{\begin{align*}#1\end{align*}}$题意：给定$n,b,c,d,e,a_{0\cdots n-1}$，令$x_k=bc^{4k}+dc^{2k}+e$，$f(x)=\sum\limits_{i=0}^{n-1}a_ix^i$，求$f(x_{0\cdots n-1})$

如果单纯看推公式的话，这题没什么思维含量，但对各种卷积的处理还是需要一定的思考的

1.$c=0$，此时$x_0=b+d+e$，$x_{1\cdots n-1}=e$，直接算即可

2.$b=0$，我们来推导一番

$\ali{f(x_k)&=\sum\limits_{i=0}^{n-1}a_i(dc^{2k}+e)^i\\&=\sum\limits_{i=0}^{n-1}a_i\sum\limits_{j=0}^i\binom ijd^jc^{2kj}e^{i-j}\\&=\sum\limits_{j=0}^{n-1}\dfrac{d^jc^{2kj}}{j!}\sum\limits_{i=j}^{n-1}\dfrac{a_ii!e^{i-j}}{(i-j)!}}$

令$p_j=\sum\limits_{i=j}^{n-1}\frac{a_ii!e^{i-j}}{(i-j)!}$，这是$a_ii!(i=n-1\cdots0)$卷$\frac{e^i}{i!}(i=0\cdots n-1)$的$n-1-j$项

$\ali{\sum\limits_{j=0}^{n-1}\dfrac{d^jc^{2kj}p_j}{j!}&=c^{k^2}\sum\limits_{j=0}^{n-1}\dfrac{c^{-(k-j)^2}c^{j^2}d^jp_j}{j!}\\&=c^{k^2}\left(\sum\limits_{j=0}^k\dfrac{c^{-(k-j)^2}c^{j^2}d^jp_j}{j!}+\sum\limits_{j=k+1}^{n-1}\dfrac{c^{-(j-k)^2}c^{j^2}d^jp_j}{j!}\right)}$

第一个sigma是$c^{-i^2}(i=0\cdots n-1)$卷$\frac{c^{i^2}d^ip_i}{i!}(i=0\cdots n-1)$的$k$项，第二个sigma是$\frac{c^{i^2}d^ip_i}{i!}(i=n-1\cdots1)$卷$c^{-i^2}(i=1\cdots n-1)$的$n-2-k$项

3.一般情况

我们先配方，$bc^{4k}+dc^{2k}+e=b\left(c^{2k}+\frac d{2b}\right)^2+e-\frac{d^2}{4b}$，重新定义$d=\frac d{2b},e=e-\frac{d^2}{4b}$，于是$x_k=b(c^{2k}+d)^2+e$

$\ali{f(x_k)&=\sum\limits_{i=0}^{n-1}a_i\left[b\left(c^{2k}+d\right)^2+e\right]^2\\&=\sum\limits_{i=0}^{n-1}a_i\sum\limits_{j=i}^{n-1}\binom ijb^j\left(c^{2k}+d\right)^{2j}e^{i-j}\\&=\sum\limits_{j=0}^{n-1}\dfrac{b^j\left(c^{2k}+d\right)^{2j}p_j}{j!}\\&=\sum\limits_{j=0}^{n-1}\dfrac{b^jp_j}{j!}\sum\limits_{l=0}^{2j}\binom{2j}lc^{2kl}d^{2j-l}\\&=\sum\limits_{l=0}^{2n-2}\dfrac{c^{2kl}}{l!}\sum\limits_{j=\left\lceil\frac l2\right\rceil}^{n-1}\dfrac{(2j)!d^{2j-l}b^jp_j}{j!(2j-l)!}}$

令$q_l=\sum\limits_{j=\left\lceil\frac l2\right\rceil}^{n-1}\frac{(2j)!d^{2j-l}b^jp_j}{j!(2j-l)!}$，下面分别对$l$为奇数和偶数的情况分开讨论，因为式子中偏移$-l$的项含$2j$，所以推式子的时候要适当换元$t=2j$

$l$为奇数，是$\frac{(2i)!b^ip_i}{i!}(i=n-1\cdots1)$卷$\frac{d^{2i-1}}{(2i-1)!}(i=1\cdots n-1)$的$n-1-\frac{l+1}2$项

$l$为偶数，是$\frac{(2i)!b^ip_i}{i!}(i=n-1\cdots0)$卷$\frac{d^{2i}}{(2i)!}(i=0\cdots n-1)$的$n-1-\frac l2$项

$\ali{\sum\limits_{l=0}^{2n-2}\dfrac{c^{2kl}q_l}{l!}&=c^{k^2}\sum\limits_{l=0}^{2n-2}\dfrac{c^{-(k-l)^2}c^{l^2}q_l}{l!}\\&=c^{k^2}\left(\sum\limits_{l=0}^k\dfrac{c^{-(k-l)^2}c^{l^2}q_l}{l!}+\sum\limits_{l=k+1}^{2n-2}\dfrac{c^{-(l-k)^2}c^{l^2}q_l}{l!}\right)}$

第一个sigma是$c^{-i^2}(i=0\cdots n-1)$卷$\frac{c^{i^2}q_i}{i!}(i=0\cdots n-1)$的$k$项，第二个sigma是$\frac{c^{i^2}q_i}{i!}(i=2n-2\cdots1)$卷$c^{-i^2}(i=1\cdots2n-2)$的$2n-3-k$项

然后就做完了，感觉略毒…

#include
#include
#include
typedef long long ll;
const int mod=1000003,maxn=524288;
typedef double du;
int mul(int a,int b){return a*(ll)b%mod;}
int ad(int a,int b){return(a+b)%mod;}
int de(int a,int b){return(a-b)%mod;}
int pow(int a,ll b){
int s=1;
while(b){
if(b&1)s=mul(s,a);
a=mul(a,a);
b>>=1;
}
return s;
}
struct complex{
du x,y;
complex(du a=0,du b=0){x=a;y=b;}
};
complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void swap(complex&a,complex&b){
complex c=a;
a=b;
b=c;
}
int rev[maxn],N;
complex w[19][maxn];
void pre(int n){
int i,j,k;
for(N=1,k=0;N>1]>>1)|((i&1)<<(k-1)); k=0; for(i=2;i<=N;i<<=1){ for(j=0;j>1;k++){
t=w[f][k];
if(on==-1)t.y=-t.y;
t=t*a[i/2+j+k];
a[i/2+j+k]=a[j+k]-t;
a[j+k]=a[j+k]+t;
}
}
f++;
}
if(on==-1){
for(i=0;i>10;
B[i]=a[i]&1023;
C[i]=b[i]>>10;
D[i]=b[i]&1023;
}
fft(A,1);
fft(B,1);
fft(C,1);
fft(D,1);
for(i=0;i0;i--)rfac[i-1]=mul(rfac[i],i);
if(c==0)
c0::solve();
else if(b==0)
b0::solve();
else
def::solve();
}