【ZJOI 2014】力

阳光穿透心脏的1/2处 2023-08-17 15:48 91阅读 0赞

# Problem #

## Description ##

给出 \\(n\\) 个数 \\(q\_i\\)，给出 \\(F\_j\\) 的定义如下：

\\\[F\_j=\\sum\_\{i<j\} \\frac\{q\_iq\_j\}\{(i-j)^2\} - \\sum\_\{i>j\} \\frac\{q\_iq\_j\}\{(i-j)^2\}\\\]

令 \\(E\_i=F\_i/q\_i\\)，求 \\(E\_i\\)。

## Input Format ##

第一行一个整数\\(n\\)。

接下来 \\(n\\) 行每行输入一个数，第 \\(i\\) 行表示 \\(q\_i\\)。

## Output Format ##

\\(n\\) 行，第 \\(i\\) 行输出 \\(E\_i\\)。与标准答案误差不超过 \\(10^\{-2\}\\) 即可。

## Sample ##

### Input ###

5
    4006373.885184
    15375036.435759
    1717456.469144
    8514941.004912
    1410681.345880

### Output ###

-16838672.693
    3439.793
    7509018.566
    4595686.886
    10903040.872

## Range ##

对于所有的数据，\\(n\\leq 100000,\\ 0<q\_i<10^9\\)。

# Algorithm #

\\(FFT\\)

# Mentality #

\\\[ E\_i=\\sum\_\{j=1\}^\{i-1\}\\frac\{q\_j\}\{(i-j)^2\}-\\sum\_\{j=i+1\}^n\\frac\{q\_j\}\{(j-i)^2\} \\\]

设 \\(g\_i=\\frac\{1\}\{i^2\}\\) ，则有：  
\\\[ E\_i=\\sum\_\{j=1\}^\{i-1\}q\_jg\_\{i-j\}-\\sum\_\{j=i+1\}^nq\_jg\_\{j-i\} \\\]  
单独算每个 \\(E\_i\\) 的前一部分，再算所有 \\(E\_i\\) 的后一部分。

由于 \\(q\_0=g\_0=0\\) ，则对于：  
\\\[ \\sum\_\{j=1\}^\{i-1\}q\_jg\_\{i-j\}=\\sum\_\{j=0\}^\{i\}q\_jg\_\{i-j\} \\\]  
直接 \\(FFT\\) 求得。

对于后一部分，将 \\(q\\) 数组翻转得到数组 \\(p\\) 。

则有：  
\\\[ \\sum\_\{j=i+1\}^nq\_jg\_\{j-i\}=\\sum\_\{j=0\}^\{n-i+1\}p\_jg\_\{n-i+1-j\} \\\]  
同样直接 \\(FFT\\) 计算。

# Code #

#include <algorithm> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; #define cp complex<double> const int Max_n = 3e5 + 5; const double pi = acos(-1); int n; int rev[Max_n]; double dv[Max_n], ans[Max_n], q[Max_n]; cp f[Max_n], g[Max_n]; namespace FFT { int lim, bit; void dft(cp *f, int t) { for (int i = 0; i < lim; i++) if (rev[i] > i) swap(f[rev[i]], f[i]); for (int len = 1; len < lim; len <<= 1) { cp Wn = exp(cp(0, t * pi / len)); for (int i = 0; i < lim; i += len << 1) { cp Wnk(1, 0); for (int k = i; k < i + len; k++, Wnk *= Wn) { cp x = f[k], y = Wnk * f[k + len]; f[k] = x + y, f[k + len] = x - y; } } } } void fft(double *a, double *b, int tot) { lim = 1, bit = 0; while (lim <= tot) lim <<= 1, bit++; for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); for (int i = 0; i < lim; i++) f[i] = a[i], g[i] = b[i]; dft(f, 1), dft(g, 1); for (int i = 0; i < lim; i++) f[i] *= g[i]; dft(f, -1); for (int i = 0; i < lim; i++) f[i] /= lim; } } // namespace FFT using namespace FFT; int main() { #ifndef ONLINE_JUDGE freopen("3338.in", "r", stdin); freopen("3338.out", "w", stdout); #endif cin >> n; for (int i = 1; i <= n; i++) scanf("%lf", &q[i]); for (int i = 1; i <= n; i++) dv[i] = (double)(1.0 / i / i); fft(q, dv, n << 1); for (int i = 1; i <= n; i++) ans[i] += f[i].real(); reverse(q + 1, q + n + 1); fft(q, dv, n << 1); for (int i = 1; i <= n; i++) printf("%.2lf\n", (ans[i] -= f[n - i + 1].real())); }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11437943.html