首先读出题意，然后发现这是一道DP，我们可以获得递推式为
然后就知道，不行啊，时间复杂度为O(n2),然后又可以根据递推式看出这里面可以拆解成多项式乘法，但是即使用了fft，我们还需要做n次多项式乘法，时间复杂度又变成O(n2 * log n)，显然不可以。然后又利用c分治思维吧问题进行拆分问题但是，前面求出来的结果对后面的结果会产生影响，所以我们使用cdq分治思想来解决这个问题，时间复杂度变为O(n * log2n)。
#include<bits/stdc++.h>
using namespace std; const double pi = acos(-1.0);
const int mod = ;
const int maxn = 4e5 + ;
int in[maxn], dp[maxn]; struct Complex{
double r,i;
Complex(double r = 0.0, double i = 0.0):r(r),i(i){};
Complex operator+(const Complex &rhs){
return Complex(r + rhs.r, i + rhs.i);
}
Complex operator-(const Complex &rhs){
return Complex(r - rhs.r, i - rhs.i);
}
Complex operator*(const Complex & rhs){
return Complex(r*rhs.r - i*rhs.i, i*rhs.r + r * rhs.i);
}
}x1[maxn],x2[maxn]; void rader(Complex *F, int len){
int j = len >> ;
for(int i = , j = len/; i < len - ; i ++){
if(i < j)swap(F[i], F[j]);
int k = len / ;
while(j >= k){
j -= k; k /= ;
}
if(j < k) j += k;
}
} void FFT(Complex *F, int len, int t){
rader(F, len);
for(int h = ; h <= len; h <<= ){
Complex wn(cos(-t**pi/h), sin(-t**pi/h));
for(int j = ; j < len; j += h){
Complex E(, );
for(int k = j; k < j + h/; k ++){
Complex u = F[k];
Complex v = E * F[k + h/];
F[k] = u + v;
F[k + h/] = u - v;
E = E * wn;
}
}
}
if(t == -)
for(int i = ; i < len; i ++)
F[i].r /= len;
} void cdq(int l, int r){
if(l == r){
dp[l] = (in[l]+dp[l])%mod;
return ;
}
int m = l + r>>;
cdq(l,m);
int len1 = r - l + ;
int len2 = m - l + ;
int len = ;while(len < (len1 + len2)) len <<= ;
for(int i = ; i < len; i ++) x1[i] = x2[i] = Complex(,);
for(int i = ; i < len2; i ++) x1[i] = Complex(dp[i + l], );
for(int i = ; i < len1; i ++) x2[i] = Complex(in[i], );
FFT(x1, len, );FFT(x2, len, ); for(int i = ; i < len; i ++) x1[i] = x1[i] * x2[i];
FFT(x1, len, -);
for(int i = m + ; i <= r; i ++) dp[i] = (dp[i] + (int)(x1[i - l].r + 0.5)) % mod;
cdq(m + , r);
} int main(){
int n;
while(~scanf("%d",&n), n){
for(int i = ; i <= n; i ++){
scanf("%d",&in[i]);
in[i] %= mod;
}
memset(dp, , sizeof(dp));
cdq(, n);
printf("%d\n", dp[n] % mod);
for(int i = ; i <= n; i ++)printf("%d ",dp[i]);printf("\n");
}
return ;
}