[ZJOI 2014] 力

发布于2016年01月03日 | 暂无评论 | 1,493阅读 | FFT,高等数学

题目描述

给出n个数qi，给出Fj的定义如下：

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

令 ${E_i} = \frac{{{F_i}}}{{{q_i}}}$ 。试求 ${E_i}$ 。

输入格式

输入文件force.in包含一个整数n，接下来n行每行输入一个数，第i行表示qi。

输出格式

输出文件force.out有n行，第i行输出Ei。与标准答案误差不超过1e-2即可。

题目解析

易得 ${E_j} = \sum\limits_{i < j} {\frac{{{q_i}}}{{{{(i - j)}^2}}}} - \sum\limits_{i > j} {\frac{{{q_i}}}{{{{(i - j)}^2}}}}$ 。发现被减数是标准的卷积形式，减数只需要把q数组反向就可变成标准的卷积形式。于是只需正向逆向各作一次卷积，相减即可。

/**************************************************************
    Problem: 3527
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:3612 ms
    Memory:20024 kb
****************************************************************/
 
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define lowbit(x) (x)&(-x)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
  
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct cpx {
    double x,y;
    cpx(double a=0,double b=0):x(a),y(b) {}
};
 
cpx operator + (cpx a,cpx b) {return cpx(a.x+b.x,a.y+b.y);}
cpx operator - (cpx a,cpx b) {return cpx(a.x-b.x,a.y-b.y);}
cpx operator * (cpx a,cpx b) {return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
 
const double pi=acos(-1.0);
void DFT(cpx* a,int n,int d=1) {
    for(int i=(n>>1),j=1;j<n;j++) {
        if(i<j) swap(a[i],a[j]);
        int k;for(k=(n>>1);i&k;i^=k,k>>=1);
        i^=k;
    }
    for(int m=2;m<=n;m<<=1) {
        cpx w=cpx(cos(pi*2/m*d),sin(pi*2/m*d));
        for(int i=0;i<n;i+=m) {
            cpx s=cpx(1,0);
            for(int j=i;j<(i+(m>>1));j++) {
                cpx u=a[j],v=s*a[j+(m>>1)];
                a[j]=u+v;a[j+(m>>1)]=u-v;
                s=s*w;
            }
        }
    }
    if(d==-1) for(int i=0;i<n;i++) a[i].x=a[i].x/n; 
}
 
const int maxn=(int)(4e5)+5;
cpx A[maxn],B[maxn];
double q[maxn],res[maxn];
int main() {
    int n,len=0;
    read(n);
    while((1<<len) < (n<<1)) len++;
    for(int i=0;i<n;i++) scanf("%lf",&q[i]);
    for(int i=0;i<n;i++) A[i]=cpx(q[i]);
    for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i);
    DFT(A,1<<len);DFT(B,1<<len);
    for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i];
    DFT(A,1<<len,-1);
    for(int i=0;i<(1<<len);i++) res[i]=A[i].x;
    for(int i=0;i<(1<<len);i++) A[i]=cpx();
    for(int i=0;i<(1<<len);i++) B[i]=cpx();
    for(int i=0;i<n;i++) A[i]=cpx(q[n-i-1]);
    for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i);
    DFT(A,1<<len);DFT(B,1<<len);
    for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i];
    DFT(A,1<<len,-1);
    for(int i=0;i<n;i++) res[i]-=A[n-i-1].x;
    for(int i=0;i<n;i++) printf("%.3lf\n",res[i]);
    return 0;
}

100

101

102

103

104

/**************************************************************

Problem: 3527

User: frank_c1

Language: C++

Result: Accepted

Time:3612 ms

Memory:20024 kb

****************************************************************/

#include <set>

#include <map>

#include <queue>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <bitset>

#include <cstring>

#include <cstdlib>

#include <utility>

#include <iostream>

#include <algorithm>

#define lowbit(x) (x)&(-x)

#define REP(i,a,b) for(int i=(a);i<=(b);i++)

#define PER(i,a,b) for(int i=(a);i>=(b);i--)

#define RVC(i,S) for(int i=0;i<(S).size();i++)

#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

template<class T> inline

void read(T& num) {

bool start=false,neg=false;

char c;

num=0;

while((c=getchar())!=EOF) {

if(c=='-') start=neg=true;

else if(c>='0' && c<='9') {

start=true;

num=num*10+c-'0';

} else if(start) break;

}

if(neg) num=-num;

}

/*============ Header Template ============*/

struct cpx {

double x,y;

cpx(double a=0,double b=0):x(a),y(b) {}

};

cpx operator + (cpx a,cpx b) {return cpx(a.x+b.x,a.y+b.y);}

cpx operator - (cpx a,cpx b) {return cpx(a.x-b.x,a.y-b.y);}

cpx operator * (cpx a,cpx b) {return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

const double pi=acos(-1.0);

void DFT(cpx* a,int n,int d=1) {

for(int i=(n>>1),j=1;j<n;j++) {

if(i<j) swap(a[i],a[j]);

int k;for(k=(n>>1);i&k;i^=k,k>>=1);

i^=k;

}

for(int m=2;m<=n;m<<=1) {

cpx w=cpx(cos(pi*2/m*d),sin(pi*2/m*d));

for(int i=0;i<n;i+=m) {

cpx s=cpx(1,0);

for(int j=i;j<(i+(m>>1));j++) {

cpx u=a[j],v=s*a[j+(m>>1)];

a[j]=u+v;a[j+(m>>1)]=u-v;

s=s*w;

}

if(d==-1) for(int i=0;i<n;i++) a[i].x=a[i].x/n;

}

const int maxn=(int)(4e5)+5;

cpx A[maxn],B[maxn];

double q[maxn],res[maxn];

int main() {

int n,len=0;

read(n);

while((1<<len) < (n<<1)) len++;

for(int i=0;i<n;i++) scanf("%lf",&q[i]);

for(int i=0;i<n;i++) A[i]=cpx(q[i]);

for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i);

DFT(A,1<<len);DFT(B,1<<len);

for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i];

DFT(A,1<<len,-1);

for(int i=0;i<(1<<len);i++) res[i]=A[i].x;

for(int i=0;i<(1<<len);i++) A[i]=cpx();

for(int i=0;i<(1<<len);i++) B[i]=cpx();

for(int i=0;i<n;i++) A[i]=cpx(q[n-i-1]);

for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i);

DFT(A,1<<len);DFT(B,1<<len);

for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i];

DFT(A,1<<len,-1);

for(int i=0;i<n;i++) res[i]-=A[n-i-1].x;

for(int i=0;i<n;i++) printf("%.3lf\n",res[i]);

return 0;

}

AC. 梦想

[ZJOI 2014] 力

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签