程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3257 ZJOI2014快速傅裡葉變換

BZOJ 3257 ZJOI2014快速傅裡葉變換

編輯:C++入門知識

BZOJ 3257 ZJOI2014快速傅裡葉變換


題目大意:給定n個點,第i個點和第j個點之間的庫侖力為(qi*qj)/(i-j)^2,定義左側為正方向,求每個點受的合力與電荷量的比值

 

 

#include 
#include 
#include 
#include 
#include 
#define M 263000
#define PI 3.1415926535897932384626433832795028841971
using namespace std;
struct Complex{
	long double a,b;
	Complex() {}
	Complex(long double _,long double __):a(_),b(__) {}
	Complex operator + (const Complex &x) const
	{
		return Complex(a+x.a,b+x.b);
	}
	Complex operator - (const Complex &x) const
	{
		return Complex(a-x.a,b-x.b);
	}
	Complex operator * (const Complex &x) const
	{
		return Complex(a*x.a-b*x.b,a*x.b+b*x.a);
	}
	void operator *= (const Complex &x)
	{
		*this=(*this)*x;
	}
}a[M],b[M],c[M];
int n;
long double q[M],ans[M];
void FFT(Complex x[],int n,int type)
{
	static Complex temp[M];
	if(n==1) return ;
	int i;
	for(i=0;i>1]=x[i],temp[i+n>>1]=x[i+1];
	memcpy(x,temp,sizeof(Complex)*n);
	Complex *l=x,*r=x+(n>>1);
	FFT(l,n>>1,type);FFT(r,n>>1,type);
	Complex root(cos(type*2*PI/n),sin(type*2*PI/n)),w(1,0);
	for(i=0;i>1;i++,w*=root)
		temp[i]=l[i]+w*r[i],temp[i+(n>>1)]=l[i]-w*r[i];
	memcpy(x,temp,sizeof(Complex)*n);
}
int main()
{
	int i,digit;
	double x;
	
	cin>>n;
	for(digit=1;digit<=n<<1;digit<<=1);

	for(i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved