洛谷P3338 [ZJOI2014]力

zrzring 2021-01-18 PM 41℃ 0条

题目要求

$$ E_i = \sum_{i = 1}^{j - 1}\frac{q_i}{(i - j)^2} - \sum_{i = j + 1}^{n}\frac{q_i}{(i - j)^2} $$

记$f(i) = q_i$,$g(i) = \displaystyle\frac{1}{i^2}$

$$ \begin{aligned} E_i &= \sum_{i = 1}^{j - 1}f(i)g(i - j) - \sum_{i = j + 1}^{n}f(i)g(i - j) \\ &= \sum_{i = 1}^{j}f(i)g(i - j) - \sum_{i = j}^{n}f(i)g(i -j) \\ &= \sum_{i = 1}^{j}f(i)g(i - j) - \sum_{i = 1}^{n - j}f(i + j)g(i) \end{aligned} $$

设$f'(i) = f(n - i)$,$t = n - j$

$$ E_i = \sum_{i = 1}^{j}f(i)g(i - j) - \sum_{i = 1}^{t}f'(t - i)g(i) $$

两项就都是卷积形式了,可以用FFT解决

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

const double pi = acos(-1.0);

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct COMP {
    double x, y;
    COMP operator + (const COMP a) const {return {x + a.x, y + a.y};}
    COMP operator - (const COMP a) const {return {x - a.x, y - a.y};}
    COMP operator * (const COMP a) const {return {x * a.x - y * a.y, x * a.y + y * a.x};}
} a[N], b[N], c[N];

int n, m, cur, rev[N];

void fft(COMP *a, int opt) {
    for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1) {
        COMP t = {cos(pi / i), sin(pi / i) * opt};
        for (int j = 0; j < n; j += i << 1) {
            COMP w = {1, 0};
            for (int k = j; k < j + i; k++) {
                COMP x = a[k], d = w * a[k + i];
                a[k] = x + d; a[k + i] = x - d; w = w * t;
            }
        }
    }
    if (opt == -1) for (int i = 0; i < n; i++) a[i].x /= n;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) scanf("%lf", &a[i].x), b[n - i] = a[i];
    for (int i = 1; i <= n; i++) c[i].x = 1.0 / (long double)i / (long double)i;
    int lg2 = 0; m = n << 1; n = 1; while (n <= m) n <<= 1, lg2++;
    for (int i = 0; i < n; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << lg2 - 1;
    fft(a, 1); fft(b, 1); fft(c, 1);
    for (int i = 0; i < n; i++) a[i] = a[i] * c[i];
    for (int i = 0; i < n; i++) b[i] = b[i] * c[i];
    fft(a, -1); fft(b, -1);
    for (int i = 1; i <= m >> 1; i++) printf("%.3lf\n", a[i] - b[(m >> 1) - i]);
    return 0;
}
Title - Artist
0:00