FFT 학습 노트

FFT 는 볼 륨 문 제 를 해결 하 는 데 사용 할 수 있다.일반적인 문제 형식 은 다음 과 같다. C = A ∗ B C [i] = ∑ ij = 0A [i] ∗ B [i − j]
만약 에 A, B 를 두 개의 횟수 로 n 다항식 A (x) = ∑ ni = 0a [i] ∗ xi, B (x) = ∑ ni = 0b [i] ∗ xi 원 문 제 는 두 개의 다항식 상승 과 같 고 C 의 횟수 는 2n - 1 과 같다.
포인트
하나의 횟수 계 가 n 인 다항식 A 의 점 수 는 n 개의 점 값 으로 구 성 된 집합 을 나타 낸다.{(x0, y0), (x1, y1)... (xn - 1, yn - 1)} 그 중에서 yi = A (xi), x 는 각각 다르다.
삽입 값
플러그 인 연산 은 점 값 연산 의 역 연산 입 니 다. n 개의 점 값 이 맞 는 점 값 표현 을 지정 하면 우 리 는 유일한 횟수 계 가 n 인 다항식 을 확정 할 수 있 습 니 다.
다항식 곱셈 에 대해 서 는 A 의 점 값 표현 {(x0, a0), (x1, a1)... (xn - 1, an - 1)} 과 B 의 점 값 표현 {(x0, b0), (x1, b1).
직접 폭력, 복잡 도 는 O (n ^ 2) 이 고 FFT 의 관건 은 x 의 선택 에 있다.
복수
형 예 를 들 어 a + bi (i = − 1 − − √) 가 평면 직각 좌표 계 를 구축 하면 a 는 x 좌표 이 고 b 는 y 좌표 로 서 우 리 는 점 대 (a, b) 로 복 수 를 표시 할 수 있 으 며 평면 벡터 에 해당 한다.삼각함수 로 간단하게 유도 하면 복수 곱셈 으로 얻 은 새로운 벡터 의 길이 가 원 벡터 의 길이 와 같 고 x 축의 협각 과 원 벡터 의 협각 의 합 을 발견 할 수 있다.
차 단위 복수 근
n 차 단위 복수 근 은 wn = 1 의 복수 w 를 만족 시 키 고 w1 ~ wn 은 평면 을 n 부 기 w 를 위주 로 n 차 단위 복수 근 으로 나 누 면 w = (cos (2 pi / n), sin (2 pi / n) wi = wi - 1 * 8727 ° w = (cos (2i pi / n), sin (2i pi / n) 은 다른 단위 의 복수 근 을 구분 하기 위해 다음 표 시 를 추가 하여 표시 한다 (win).
도 리 를 없애다.
wdkdn=wkn wdkdn=(cos(2dkπ/(dn)),sin(2dkπ/(dn)))=(cos(2kπ/n),sin(2kπ/n))=wkn
절반 으로 이 치 를 따지다.
2n 차 단위 복수 근 의 제곱 집합 은 n 차 단위 복수 근 의 집합 과 같다.임의의 < = n 의 k 에 대해 유일한 < = n 의 k '가 존재 한 다 는 것 을 알 수 있다.
구 화인 리
k!=0, n > 0 시 ∑ n − 1i = 0wkin = 0 은 등비 수열 구 화 에 해당 하고 ∑ n − 1i = 0wkin = (wknn − w0n) / (wk − 1) = 0
FFT
편 의 를 위해 서, 우 리 는 횟수 n = 2 ^ k 의 다항식 곱셈 만 을 고려 하여 어떻게 단일 수 x 의 함수 값 A (x) 를 구 합 니까?우 리 는 두 개의 다항식 A0 (x) = a0 + a2x + a4x 2 ⋅ ⋅ an − 2xn / 2 A1 (x) = a1 + a3x + a5x 2 ⋅ ⋅ an − 1xn / 2 A (x) = A0 (x2) + x ∗ A1 (x2) 의 원래 문제: A (x) 가 n 차 단위 복수 근 에 있 는 함수 값 을 구 합 니 다.전환: A0 (x) 과 A1 (x) 이 n / 2 차 단위 복수 근 에 있 는 값 을 구하 십시오.따라서 n / 2 의 다항식 A0 (x) 과 A1 (x) 을 n / 2 개의 n / 2 차 단위 복수 근 에서 재 귀적 으로 값 을 구 할 수 있다.
삽입 값 연산 은 점 값 연산 을 행렬 방정식 의 형식 으로 쓰 면 표현 식 Y = Vn * 8727 ° A 를 얻 을 수 있 습 니 다.그러면 삽입 값 연산 은 A, A = V − 1n ∗ Y 를 구 하 는 것 과 같다
결론, V - 1n [j, k] = w - jkn / n. 증명: [Vn - 8727 ° V - 1n] [j, j '] = ∑ n - 1i = 0w (j' - j) in / n, 만약 j '= j 라면 그 뒤 는 1 이 고 그렇지 않 으 면 구 와 인용 에 따라 0 이다.
최 적 화 를 실현 하 다
어떻게 공간의 복잡 도 를 O (n) 로 낮 춥 니까?글 쎄 요. 코드 를 자세히 보 세 요.

struct z{
    double x,y;
    z(double _x=0,double _y=0){x=_x,y=_y;}
}c[maxn],d[maxn],g[maxn],a[maxn],b[maxn],an[maxn];
z operator *(z a,z b){return z(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
z operator +(z a,z b){return z(a.x+b.x,a.y+b.y);}
z operator -(z a,z b){return z(a.x-b.x,a.y-b.y);}
void dft(ar *a,int sig){
    int i,m=1,k,half,j;
    fo(i,0,l-1) g[f[i]]=a[i];
    while (m;
        fo(k,0,half-1){
            ar w=ar(cos(pi*sig*k/half),sin(pi*sig*k/half));
            for(i=k;i
                j=i+half;
                ar u=g[i],v=w*g[j];
                g[i]=u+v,g[j]=u-v;
            }
        }
    }fo(i,0,l-1)a[i]=g[i];
    if (sig<0) fo(i,0,l-1) a[i].x/=l;
}
void fft(){
    fo(i,0,l-1) a[i]=b[i]=z(0,0);
    fo(i,0,n) a[i].x=a1[i],b[i].x=b1[i];
    dft(a,1),dft(b,1);
    fo(i,0,l-1) an[i]=a[i]*b[i];
    dft(an,-1);
    fo(i,0,l-1) ans[i]=(ll)(an[i].x+eps);
}
void chu(){
    l=1,t=0;
    while (l<=n*2) l+=l,t++;
    fo(i,0,l-1){
        int x=i,y=t-1;f[i]=0;
        while (x) f[i]+=(x&1)<>=1;
    }
}