Power oj 2540 (FFT卷积)
发布日期:2021-06-29 21:40:30 浏览次数:2 分类:技术文章

本文共 2144 字,大约阅读时间需要 7 分钟。

题目链接:https://www.oj.swust.edu.cn/problem/show/2540

代码:

#include<bits/stdc++.h>

using namespace std;
const int FFT_MAXN = 1 << 18;
const double pi = acos(-1.0);
struct Complex
{
    double R, I;
    inline Complex(double real = 0.0, double image = 0.0)
    {
        R = real, I = image;
    }
    inline Complex operator + (Complex const &b) const
    {
        return Complex(R + b.R, I + b.I);
    }
    inline Complex operator - (Complex const &b) const
    {
        return Complex(R - b.R, I - b.I);
    }
    inline Complex operator * (Complex const &b) const
    {
        return Complex(R * b.R - I * b.I, I * b.R + R * b.I);
    }
} Wn[FFT_MAXN + 1];
int bitrev[FFT_MAXN];
inline int getLength(int n, int m)
{
    n = n + m - 1;
    int i = 1;
    for(; i < n; i <<= 1);
    return i;
}
void Change(Complex a[], int n)
{
    int d = 0;
    while((1 << d)*n != FFT_MAXN)
        d++;
    for(int i = 0; i < n; i++)
        if(i < (bitrev[i] >> d))
            swap(a[i], a[bitrev[i] >> d]);
}
void FFT(Complex P[], int n, int op)
{
    Change(P, n);
    for(int len = 2; len <= n; len <<= 1)
    {
        int m = len >> 1;
        int del = FFT_MAXN / len * op;
        for(int i = 0; i < n; i += len)
        {
            Complex *p = P + i, *q = P + i + m, *w = op == 1 ? Wn : Wn + FFT_MAXN;
            for(int j = 0; j < m; j++, p++, q++, w += del)
            {
                Complex ne = *q * *w;
                *q = *p - ne;
                *p = *p + ne;
            }
        }
    }
    if(op == -1)
        for(int i = 0; i < n; i++)
        {
            P[i].R /= n;
            P[i].I /= n;
        }
}
void FFTInit()
{
    int L = 0;
    while((1 << L) != FFT_MAXN)
        L++;
    bitrev[0] = 0;
    for(int i = 1; i < FFT_MAXN; i++)
        bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
    for(int i = 0; i <= FFT_MAXN; i++)
        Wn[i] = Complex(cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i));
}
Complex A[FFT_MAXN], B[FFT_MAXN];
int main()
{
    FFTInit();
    int n, m;
    scanf("%d%d", &n, &m);
    int N = getLength(n, m);
    for(int i = 0; i < N; i++)
    {
        if(i < n)
        {
            int x;
            scanf("%d", &x);
            A[i] = Complex(x, 0);
        }
        else A[i] = Complex();
    }
    for(int i = 0; i < N; i++)
    {
        if(i < m)
        {
            int y;
            scanf("%d", &y);
            B[i] = Complex(y, 0);
        }
        else B[i] = Complex();
    }
    FFT(A, N, 1);
    FFT(B, N, 1);
    for(int i = 0; i < N; i++)
        A[i] = A[i] * B[i];
    FFT(A, N, -1);
    for(int i = 0; i <= n + m - 2; i++)
    {
        if(i == 0) printf("%d", (int)(A[i].R+0.5 ));
        else printf(" %d", (int)(A[i].R+0.5));
    }
    printf("\n");
    return 0;
}

 

 

 

转载地址:https://dh-butterfly.blog.csdn.net/article/details/77451746 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu 6165(dfs or bfs or tarjan+topsort)
下一篇:hdu 6158(数学定理)

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年04月16日 12时28分37秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章