专栏首页数据结构与算法BZOJ3527: [Zjoi2014]力(FFT)

BZOJ3527: [Zjoi2014]力(FFT)

题意

题目链接

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P2196 挖地雷(dp)

    attack
  • 洛谷P3380 【模板】二逼平衡树(树套树)

    您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

    attack
  • Codeforces Round #490 (Div. 3)

    attack
  • 家谱树

    【问题描述】     有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。     给出每个人的孩子的信息。     输出一个序列,使得每个人的后辈都比那...

    attack
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • 八数码难题解法大全

    暂时弃坑,双向广搜太难写了。。。。 https://www.luogu.org/problem/show?pid=1379 突然发现八数码难题挺有意思的 貌似关...

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack
  • OpenCV图像处理专栏九 | 基于直方图的快速中值滤波算法

    这是OpenCV图像处理专栏的第9篇文章,主要介绍一个基于直方图的快速中值滤波算法,希望对大家有帮助。

    BBuf
  • 2017.10.2解题报告

    预计分数:60+0+30=90 实际分数:60+0+0=60 T1:https://www.luogu.org/problem/show?pid=T...

    attack
  • C++创建一个名为Ellipse的椭圆类--练习

    Enterprise_

扫码关注云+社区

领取腾讯云代金券