题意：
解：
介绍两种方法。
首先可以把那个最后除的q拆掉。
①分前后两部分处理。
前一部分可以看做是个卷积。下面的平方不拆开，直接看成g即可。
后一部分按照套路，把循环变量改成从0开始，反转q，之后也是卷积。
②直接构造函数卷积。
题解。
我写的第一种。
#include <cstdio>
#include <algorithm>
#include <cmath> const int N = ;
const double pi = 3.1415926535897932384626; struct cp {
double x, y;
cp(double X = , double Y = ) {
x = X;
y = Y;
}
inline cp operator +(const cp &w) const {
return cp(x + w.x, y + w.y);
}
inline cp operator -(const cp &w) const {
return cp(x - w.x, y - w.y);
}
inline cp operator *(const cp &w) const {
return cp(x * w.x - y * w.y, x * w.y + y * w.x);
}
}f[N << ], g[N << ], h[N << ]; int r[N << ]; inline void FFT(int n, cp *a, int f) {
for(int i = ; i < n; i++) {
if(i < r[i]) {
std::swap(a[i], a[r[i]]);
}
} for(int len = ; len < n; len <<= ) {
cp Wn(cos(pi / len), f * sin(pi / len));
for(int i = ; i < n; i += (len << )) {
cp w(, );
for(int j = ; j < len; j++) {
cp t = a[i + len + j] * w;
a[i + len + j] = a[i + j] - t;
a[i + j] = a[i + j] + t;
w = w * Wn;
}
}
} if(f == -) {
for(int i = ; i <= n; i++) {
a[i].x /= n;
}
}
return;
} int main() {
int n;
scanf("%d", &n);
n--;
for(int i = ; i <= n; i++) {
scanf("%lf", &f[i].x);
h[n - i].x = f[i].x;
}
g[].x = ;
for(int i = ; i <= n; i++) {
g[i].x = ((double)()) / i / i;
} int len = , lm = ;
while(len <= n + n) {
len <<= ;
lm++;
}
for(int i = ; i <= len; i++) {
r[i] = (r[i >> ] >> ) | ((i & ) << (lm - ));
} FFT(len, f, );
FFT(len, g, );
FFT(len, h, );
for(int i = ; i <= len; i++) {
f[i] = f[i] * g[i];
g[i] = g[i] * h[i];
}
FFT(len, f, -);
FFT(len, g, -); for(int i = ; i <= n; i++) {
printf("%lf\n", f[i].x - g[n - i].x);
} return ;
}
AC代码