【题解】LOJ 2200 「ZJOI2014」力

请注意,本文编写于 97 天前,最后修改于 97 天前,其中某些信息可能已经过时。

Problem

$$ F_j=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum_{i>j}\frac{q_iq_j}{(i-j)^2} $$

求 $\frac{F_i}{q_i}$

Thought

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

设 $g[i]=\frac{1}{i^2},g[-i]=-\frac{1}{i^2}$,代入

$$ \frac{F_j}{q_j}=\sum_{i=1}^n q_ig_{j-i} $$

卷积,完了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const double pi = acos(-1);
struct Complex {
    double x, y;
    Complex operator + (const Complex o) const {return {x + o.x, y + o.y};}
    Complex operator - (const Complex o) const {return {x - o.x, y - o.y};}
    Complex operator * (const Complex o) const {return {x * o.x - y * o.y, x * o.y + y * o.x};}
};
int n, m, oldn;
int rev[N << 2], l;
Complex a[N << 2], b[N << 2];
void DFT(Complex *now, int f) {
    for(int i = 0; i < n; ++ i)
        if(i < rev[i])
            swap(now[i], now[rev[i]]);
    for(int i = 1; i < n; i <<= 1) {
        Complex wn = {cos(pi / i), f * sin(pi / i)};
        for(int j = 0; j < n; j += (i << 1)) {
            Complex w = {1, 0}, x, y;
            for(int k = 0; k < i; ++ k, w = w * wn) {
                x = now[j + k];
                y = now[i + j + k] * w;
                now[j + k] = x + y;
                now[i + j + k] = x - y;
            }
        }
    }
    if(f == - 1)
        for(int i = 0; i < n; ++ i)
            now[i].x /= n;
}
int main() {
    oldn = n = read();
    for(int i = 0; i < n; ++ i)
        scanf("%lf", &a[i].x);
    m = 2 * n - 1;
    for(int i = 0; i < n - 1; ++ i) b[i].x = - 1.0 / (1.0 * (n - i - 1) * (n - i - 1));
    for(int i = n; i < m; ++ i) b[i].x = 1.0 / (1.0 * (i + 1 - n) * (i + 1 - n));
    for(n = 1; n <= m; n <<= 1) ++ l;
    for(int i = 1; i < n; ++ i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    DFT(a, 1); DFT(b, 1);
    for(int i = 0; i < n; ++ i)
        a[i] = a[i] * b[i];
    DFT(a, - 1);
    for(int i = oldn - 1; i < m; ++ i)
        printf("%.6f\n", a[i].x);
    return 0;
}
Comments

添加新评论