欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ3527: [Zjoi2014]力(FFT)

程序员文章站 2022-06-24 14:14:36
题意 "题目链接" Sol 直接把$q_i$除掉 那么$E_j = \sum_{i = 1}^{j 1} q_i (i j)^2 \sum_{i = j + 1}^n q_i (i j)^2$ 设$f_i = q_i, g_i = i^2$ 带入原式发现原式变成了卷积的形式 $E_j = f_i g ......

题意

题目链接

sol

直接把\(q_i\)除掉

那么\(e_j = \sum_{i = 1}^{j - 1} q_i (i - j)^2 - \sum_{i = j + 1}^n q_i (i - j)^2\)

\(f_i = q_i, g_i = i^2\)

带入原式发现原式变成了卷积的形式

\(e_j = f_i g_{i - j}\)

然后像\(bzoj2194\)那样把\(g\)给翻转掉,就成了标准卷积形式

fft一波

// luogu-judger-enable-o2
#include<bits/stdc++.h>
const double pi = acos(-1);
using namespace std;
const int maxn = 1e6 + 10;
int n, m, r[maxn];
struct com {
    double x, y;
    com(double xx = 0, double yy = 0) {x = xx; y = yy;}
    com operator + (com &rhs) {
        return com(x + rhs.x, y + rhs.y);
    }
    com operator - (com &rhs) {
        return com(x - rhs.x, y - rhs.y);
    }
    com operator * (com &rhs) {
        return com(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
    }
}a[maxn], b[maxn], c[maxn];
void fft(com *a, int n, int type) {
    for(int i = 0; i < n; i++) if(i < r[i]) swap(a[i], a[r[i]]);
    for(int mid = 1; mid < n; mid <<= 1) {
        com wn(cos(pi / mid), type * sin(pi / mid)); 
        for(int r = mid << 1, j = 0; j < n; j += r) {//这里要写<n 
            com w(1, 0);
            for(int k = 0; k < mid; k++, w = w * wn) {
                com x = a[j + k], y = w * a[j + k + mid];
                a[j + k] = x + y;
                a[j + k + mid] = x - y;
            }
        }
    }
    if(type == -1) {
        for(int i = 0; i <= n; i++) a[i].x /= n;
    }
}
int mul(com *c, com *a, com *b, int n, int m) {
    int ret = 1, l = 0;
    while(ret <= n + m) ret <<= 1, l++; 
    for(int i = 0; i < ret; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1)  << l - 1);
    fft(a, ret, 1); 
    fft(b, ret, 1);
    for(int i = 0; i <= ret; i++) c[i] = a[i] * b[i];
    fft(c, ret, -1);
    return ret;
}
int main() {
    scanf("%d", &n); n -= 1;
    for(int i = 0; i <= n; i++) scanf("%lf", &a[i].x);
    for(int i = 0; i < n; i++) b[i].x = -1.0 / (double)(n - i) / (double)(n - i);
    for(int i = n + 1; i <= 2 * n; i++) b[i].x = -b[2 * n - i].x;
    mul(c, a, b, n, 2 * n);
    for(int i = n; i <= n * 2; i++) printf("%.5lf\n", c[i].x);
    return 0;
}