[ZJOI 2014]力

时间：2023-03-09 04:05:01
[ZJOI 2014]力

Description

给出n个数qi，给出Fj的定义如下：
$$F_j = \sum_{i<j}\frac{q_i q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_i q_j}{(i-j)^2 }$$
令Ei=Fi/qi，求Ei.

Input

第一行一个整数n。
接下来n行每行输入一个数，第i行表示qi。
n≤100000，0<qi<1000000000

Output

n行，第i行输出Ei。与标准答案误差不超过1e-2即可。

Sample Input

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

Sample Output

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

题解

约掉 $q_i$ $$E_j = \sum_{i<j}\frac{q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_j}{(i-j)^2 }$$

我们拿出 $A_i=\sum\limits_{i<j}\frac{q_j}{(i-j)^2 }$ 讨论。

构造第一个多项式系数依次为 $q_i,i\in[0,n)$ ，第二个多项式系数 $\begin{cases}0 &i=0\\ \frac{1}{i^2} &i\in[1,n)\end{cases}$

卷积之后第 $i$ 项就是所求的 $A_i$ 。之后的类似，对于 $A'_i=\sum\limits_{i>j}\frac{q_j}{(i-j)^2 }$ 只要把第一个多项式翻转，卷积后第 $n-1-i$ 项就是所求的 $A'_i$ 。

 //It is made by Awson on 2018.1.28

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <complex>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define dob complex<double>

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 #define writeln(x) (write(x), putchar('\n'))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = *;

 const double pi = acos(-1.0);

 int n, m, s, L, R[N+];

 double q[N+], sum, ans[N+];

 dob a[N+], b[N+];

 void FFT(dob *A, int o) {

     for (int i = ; i < n; i++) if (i > R[i]) swap(A[i], A[R[i]]);

     for (int i = ; i < n; i <<= ) {

     dob wn(cos(pi/i), sin(pi*o/i)), x, y;

     for (int j = ; j < n; j += (i<<)) {

         dob w(, );

         for (int k = ; k < i; k++, w *= wn) {

         x = A[j+k], y = w*A[i+j+k];

         A[j+k] = x+y, A[i+j+k] = x-y;

         }

     }

     }

 }

 void work() {

     scanf("%d", &n); n--; s = n;

     for (int i = ; i <= n; i++) scanf("%lf", &q[i]), a[i] = q[i];

     for (int i = ; i <= n; i++) b[i] = ./i/i;

     m = n<<; for (n = ; n <= m; n <<= ) L++;

     for (int i = ; i < n; i++) R[i] = (R[i>>]>>)|((i&)<<(L-));

     FFT(a, ), FFT(b, );

     for (int i = ; i <= n; i++) a[i] *= b[i];

     FFT(a, -);

     for (int i = ; i <= s; i++) ans[i] = a[i].real()/n;

     for (int i = ; i <= n; i++) a[i] = ;

     for (int i = ; i <= s; i++) a[i] = q[s-i];

     FFT(a, );

     for (int i = ; i <= n; i++) a[i] *= b[i];

     FFT(a, -);

     for (int i = ; i <= s; i++) printf("%lf\n", ans[i]-a[s-i].real()/n);

 }

 int main() {

     work();

     return ;

 }

相关文章