P3803 FFT求多项式系数

传送门：https://www.luogu.org/problemnew/show/P3803

题意：

这是一道FFT模板题，求多项式系数

题解：

对a和b的系数求一个fft，转换为点乘式后

O（n）扫一遍直接算系数即可

对于多项式相加

\(\begin{array}{l}{A(x)=\left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right) \ldots\left(x_{n}, y_{n}\right)} \\ {B(x)=\left(x_{0}, y_{0}^{\prime}\right),\left(x_{1}, y_{1}^{\prime}\right) \ldots .\left(x_{n}, y_{n}\right)}\end{array}\)

\(A(x)+B(x)=\left(x_{0}, y_{0}+y_{0}^{\prime}\right),\left(x_{1}, y_{1}+y_{1}^{\prime}\right)\left(x_{n}, y_{n}+y_{n}^{\prime}\right)\)

对于多项式相乘，我们需要补上一些项使得最后乘的的系数个数为2n+1

\(\begin{array}{l}{A(x)=\left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right) \ldots\left(x_{2 n}, y_{2 n}\right)} \\ {B(x)=\left(x_{0}, y_{0}^{\prime}\right),\left(x_{1}, y_{1}^{\prime}\right) \ldots .\left(x_{2 n}, y_{2 n}\right)}\end{array}\)

\(A(x) B(x)=\left(x_{0}, y_{0} y_{0}^{\prime}\right),\left(x_{1}, y_{1} y_{1}^{\prime}\right)\left(x_{2 n}, y_{2 n} y_{2 n}^{\prime}\right)\)

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 1e7 + 5;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const double Pi = acos(-1.0);

LL quick_pow(LL x, LL y) {

    LL ans = 1;

    while(y) {

        if(y & 1) {

            ans = ans * x % mod;

        } x = x * x % mod;

        y >>= 1;

    } return ans;

}

struct complex {

    double x, y;

    complex(double xx = 0, double yy = 0) {

        x = xx, y = yy;

    }

} a[maxn], b[maxn];

complex operator + (complex a, complex b) {

    return complex(a.x + b.x, a.y + b.y);

}

complex operator - (complex a, complex b) {

    return complex(a.x - b.x, a.y - b.y);

}

complex operator * (complex a, complex b) {

    return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);

}

int n, m;

int l, r[maxn];

int limit = 1;

void fft(complex *A, int type) {

    for(int i = 0; i < limit; i++) {

        if(i < r[i]) swap(A[i], A[r[i]]);

    }

    for(int mid = 1; mid < limit; mid <<= 1) {

        complex Wn(cos(Pi / mid), type * sin(Pi / mid));

        for(int R = mid << 1, j = 0; j < limit; j += R) {

            complex w(1, 0);

            for(int k = 0; k < mid; k++, w = w * Wn) {

                complex x = A[j + k], y = w * A[j + mid + k];

                A[j + k] = x + y;

                A[j + mid + k] = x - y;

            }

        }

    }

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    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(limit <= n + m) limit <<= 1, l++;

    for(int i = 0; i < limit; i++) {

        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

    }

    fft(a, 1);

    fft(b, 1);

    for(int i = 0; i <= limit; i++) {

        a[i] = a[i] * b[i];

    }

    fft(a, -1);

    for(int i = 0; i <= n + m; i++) {

        printf("%d ", (int)(a[i].x / limit + 0.5));

    }

    printf("\n");

    return 0;

}

巴特西

P3803 FFT求多项式系数

P3803 FFT求多项式系数

题意：

题解：

代码：

最新文章

热门文章