Tổng Hợp Thuật Toán Đa Thức

Phép Nhân Đa Thức

Biến Đổi Fourier Nhanh (FFT):


struct ComplexNumber {
    double real, imag;
    ComplexNumber operator + (const ComplexNumber &a) {
        return {real + a.real, imag + a.imag};
    }
    ComplexNumber operator - (const ComplexNumber &a) {
        return {real - a.real, imag - a.imag};
    }
    ComplexNumber operator * (const ComplexNumber &a) {
        return {real*a.real - imag*a.imag, real*a.imag + imag*a.real};
    }
} X[1<<18], Y[1<<18], Z[1<<18];

int rev[1<<18];
void FFT(ComplexNumber *arr, int n, int dir) {
    for(int i=0; i

Biến Đổi Số Học Nhanh (NTT):


long long power(long long a, long long b, long long mod) {
    long long res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long MOD = 998244353;
long long A[1<<18], B[1<<18], C[1<<18];
long long roots[1<<18], inv_roots[1<<18], rev_idx[1<<18];

void precompute(int n) {
    for(int i=1; i

Phân Chia CDQ Với NTT:


long long f[1<<18], g[1<<18];
void divide_conquer(int l, int r) {
    if(l == r) return;
    int mid = (l + r)/2;
    divide_conquer(l, mid);
    
    // Tính toán ảnh hưởng từ nửa trái sang nửa phải
    static long long tmp[1<<18];
    int len = r - l;
    for(int i=0; i

Nghịch Đảo Đa Thức:


void poly_inverse(int n, long long *a, long long *b) {
    if(n == 1) {
        b[0] = power(a[0], MOD-2, MOD);
        return;
    }
    poly_inverse((n+1)/2, a, b);
    
    static long long tmp[1<<18];
    int len = 1;
    while(len < n*2) len <<= 1;
    
    for(int i=0; i

Logarithm Đa Thức:


void poly_ln(int n, long long *a, long long *b) {
    static long long deriv[1<<18], inv[1<<18];
    for(int i=0; i

Thẻ: FFT NTT phân chia CDQ nghịch đảo đa thức logarit đa thức

Đăng vào ngày 28 tháng 7 lúc 16:08

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn