BZOJ 2179 FFT 빠른 부립엽 FFT
CODE:
#include
#include
#include
#include
#include
#define MAX 140010
#define PI 3.1415926535897932384626
using namespace std;
struct Complex{
double real,imag;
Complex(double _,double __):real(_),imag(__) {}
Complex() {}
Complex operator +(const Complex &a)const {
return Complex(real + a.real,imag + a.imag);
}
Complex operator -(const Complex &a)const {
return Complex(real - a.real,imag - a.imag);
}
Complex operator *(const Complex &a)const {
return Complex(real * a.real - imag * a.imag,real * a.imag + imag * a.real);
}
void operator *=(const Complex &a) {
*this = *this * a;
}
void Read() {
int temp;
scanf("%1d",&temp);
real = temp;
}
}a[MAX],b[MAX],ans[MAX];
int n;
int out[MAX];
void FFT(Complex x[],int n,int flag)
{
static Complex temp[MAX];
if(n == 1) return ;
for(int i = 0; i < n; i += 2)
temp[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,flag),FFT(r,n >> 1,flag);
Complex unit(cos(flag * 2 * PI / n),sin(flag * 2 * PI / n)),w(1.0,.0);
for(int i = 0; i < (n >> 1); ++i,w *= unit)
temp[i] = l[i] + w * r[i],temp[i + (n >> 1)] = l[i] - w * r[i];
memcpy(x,temp,sizeof(Complex) * n);
}
int main()
{
cin >> n;
for(int i = n - 1; ~i; --i)
a[i].Read();
for(int i = n - 1; ~i; --i)
b[i].Read();
int l;
for(l = 1; l <= (n << 1); l <<= 1);
FFT(a,l,1),FFT(b,l,1);
for(int i = 0; i < l; ++i)
ans[i] = a[i] * b[i];
FFT(ans,l,-1);
for(int i = 0; i < l; ++i)
out[i] = int(ans[i].real / l + .5);
int temp = 0;
for(int i = 0; i < l; ++i) {
out[i] += temp;
temp = out[i] / 10;
out[i] %= 10;
}
while(temp) out[l++] = temp % 10,temp /= 10;
while(!out[l - 1]) --l;
for(int i = l - 1; ~i; --i)
printf("%d",out[i]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STC12C5201AD 샘플링 + 직렬 전송 템플릿텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.