题意
给出(n)个数(q_i),给出(Fj)的定义如下：
[F_j=sum limits _ {i < j} frac{q_iq_j}{(i-j)^2}-sum limits _{i >j} frac{q_iq_j}{(i-j)^2}.
]
令(E_i=F_i/q_i)，求(E_i).
题解
一开始没发现求(E_i)... 其实题目还更容易想了...
[E_i=sumlimits _{j<i}frac{q_j}{(i-j)^2}-sumlimits _{j>i}frac{q_j}{(i-j)^2}
]
这个东西就是转换成求两个一样的东西就行了。
就是求$$sum_i=sum limits_{j<i} frac{q_j}{(i-j)^2}$$.
这个就是可以转换成求一个卷积形式就行了。
注意多项式乘法格式是这样的：
[A_0+A_1x+...+A_nx^n
]
[B_0+B_1x+...+B_nx^n
]
令(A)与(B)的卷积为(C),则$$C_i=sum limits {j le i}A_j*B{i-j}$$.
发现(i-j)那个形式似乎就可以满足本题的形式。
所以令(B_i=frac{1}{i^2})就行了，然后(A_i=q_i).
对于这个求两边卷积就行了23333
注意有的细节要处理一下，就是要清空一些数组，
注意一下下标（思维要清楚），而且也要令(A_0=B_0=0)。
而且之前求(B_i)的时候，(i^2)会爆long long ！
代码
/**************************************************************
Problem: 3527
User: zjp_shadow
Language: C++
Result: Accepted
Time:3688 ms
Memory:32012 kb
****************************************************************/
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("P3527.in", "r", stdin);
freopen ("P3527.out", "w", stdout);
#endif
}
struct Complex {
double re, im;
};
inline Complex operator + (const Complex &lhs, const Complex &rhs) {
return (Complex) {lhs.re + rhs.re, lhs.im + rhs.im};
}
inline Complex operator - (const Complex &lhs, const Complex &rhs) {
return (Complex) {lhs.re - rhs.re, lhs.im - rhs.im};
}
inline Complex operator * (const Complex &lhs, const Complex &rhs) {
return (Complex) {lhs.re * rhs.re - lhs.im * rhs.im, lhs.re * rhs.im + rhs.re * lhs.im};
}
const int N = 1 << 19;
int n_, n;
double f[N], g[N];
const double Pi = acos(-1.0);
int r[N];
void FFT(Complex P[], int opt) {
For (i, 0, n - 1) if (i < r[i]) swap(P[i], P[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
Complex Wi = (Complex) {cos(2 * Pi / i), opt * sin(2 * Pi / i)};
int p = i / 2;
for (int j = 0; j < n; j += i) {
Complex x = (Complex) {1.0, 0.0};
For (k, 0, p - 1) {
Complex u = P[j + k], v = x * P[j + k + p];
P[j + k] = u + v;
P[j + k + p] = u - v;
x = x * Wi;
}
}
}
}
int m;
void Mult(Complex a[], Complex b[]) {
int cnt = 0;
for (n = 1; n <= m; n <<= 1) ++ cnt;
For (i, 1, n - 1)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (cnt - 1) );
FFT(a, 1); FFT(b, 1);
For (i, 0, n - 1) a[i] = a[i] * b[i];
FFT(a, -1);
For (i, 0, n - 1) a[i].re = a[i].re / n;
}
double ans[N];
Complex a[N], b[N];
int main () {
//int n1 = read(), n2 = read(),
File();
n_ = read();
m = n_ + n_;
For (i, 1, n_) {
scanf("%lf", &f[i]);
g[i] = (double)1.0 / ((long long)i * (long long)i);
}
For (i, 0, n_) a[i].re = f[i], a[i].im = 0;
For (i, 0, n_) b[i].re = g[i], b[i].im = 0;
Mult(a, b);
For (i, 1, n_)
ans[i] += a[i].re;
reverse(f + 1, f + 1 + n_);
For (i, 0, n - 1) a[i].re = f[i], a[i].im = 0;
For (i, 0, n - 1) b[i].re = g[i], b[i].im = 0;
Mult(a, b);
For (i, 1, n_)
ans[n_ - i + 1] -= a[i].re;
For (i, 1, n_)
printf ("%.4lf
", ans[i]);
return 0;
}