课堂笔记。但是字有点小~，有需取

C++

#include<bits/stdc++.h>
using namespace std ;



const int N = 3E5+10 ;
const double PI = acos(-1) ;

int n , m ;
struct Complex
{
    double x ,y ;
    Complex operator+ (const Complex &t ) const 
    {
        return {x + t.x , y + t.y} ;
    }
    Complex operator- (const Complex &t ) const 
    {
        return {x - t.x , y - t.y}  ;
    }
    Complex operator* (const Complex &t) const 
    {
        return {x * t.x - y * t.y , x * t.y + y * t.x} ;
    }
}a[N] , b[N] ;

int rev[N] , bit , tot  ;

void fft(Complex a[]  , int inv)
{
    for(int i = 0 ; i < tot ; i ++ ) 
    {
        if(i < rev[i]) 
        {
            swap(a[i] , a[rev[i]]) ;
        }
    }

    for(int mid = 1 ; mid < tot ; mid *= 2 ) 
    {
        auto w1 = Complex({cos(PI/mid) , inv * sin(PI/mid)}) ;
        for(int i = 0 ; i < tot ; i += mid *2  ) 
        {
            auto wk = Complex({1,0}) ;
            for(int j = 0 ; j < mid ; j ++ , wk = wk * w1 ) 
            {
                auto x = a[i+j] , y = wk * a[i+j+mid] ;
                a[i+j] = x+y , a[i+j+mid] = x - y ; 
            }
        }
    }
}

int main()
{
    scanf("%d%d" , &n,&m) ;
    for(int i = 0 ; i <= n ; i ++ ) scanf("%lf" , &a[i].x) ;
    for(int i = 0 ; i <= m ; i ++ ) scanf("%lf" , &b[i].x) ;

    while((1 << bit) < n + m + 1 )  bit ++ ;
    tot = 1 << bit ;
    for(int i = 0 ; i < tot ; i ++ ) 
    {
        rev[i] = (rev[i >> 1 ] >>  1 )| ((i&1) << (bit -1 )) ;
    }

    fft(a , 1 )  , fft(b , 1 ) ;
    for(int i =  0; i  < tot ; i ++ )  a[i] = a[i] * b[i] ;

    fft(a , -1 ) ;

    for(int i = 0 ; i <= n+m ; i ++ ) 
    {
        printf("%.0lf ",a[i].x /  tot + 0.4) ; // 不加小于0.5的数字，可能出现 -0 的现象 导致错误
    }

    return 0 ;
}

不经常用就很容易忘记，比如我现在就忘了…