1 条题解

  • 1
    @ 2025-1-18 14:53:54
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <complex>
    using namespace std;
    const int N = 1e6 + 5;
    const double pi = 3.14159265358979;
    struct comp 
    {
        double x, y;
        comp(double x = 0.0, double y = 0.0) : x(x), y(y) { }
        comp operator+(const comp &o) const 
        {
            return comp(x + o.x, y + o.y);
        }
        comp operator-(const comp &o) const 
        {
            return comp(x - o.x, y - o.y);
        }
        comp operator*(const comp &o) const 
        {
            return comp(x * o.x - y * o.y, x * o.y + y * o.x);
        }
    };
    comp _x1[N], _x2[N];
    char s1[N], s2[N];
    int ans[N], rev[N], len = 1;
    void fft(comp y[], int op) 
    {
        for (int i = 0; i < len; ++i)
            if (i < rev[i])
                swap(y[i], y[rev[i]]);
    
        for (int h = 2; h <= len; h <<= 1) 
        {
            comp om(cos(2 * pi / h), sin(op * 2 * pi / h));
    
            for (int j = 0; j < len; j += h) 
            {
                comp w(1, 0);
    
                for (int k = j; k < j + h / 2; ++k) 
                {
                    comp u = y[k];
                    comp t = w * y[k + h / 2];
                    y[k] = u + t;
                    y[k + h / 2] = u - t;
                    w = w * om;
                }
            }
        }
    
        if (op == -1)
            for (int i = 0; i < len; ++i)
                y[i].x /= (double)len, y[i].y /= (double)len;
    }
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
    
        while (len <= n + m)
            len <<= 1;
    
        for (int i = 0; i <= n; ++i) 
        {
            int x;
            scanf("%d", &x);
            _x1[i].x = double(x);
        }
    
        for (int i = 0; i <= m; ++i) 
        {
            int x;
            scanf("%d", &x);
            _x2[i].x = double(x);
        }
    
        for (int i = 0; i < len; ++i) 
        {
            rev[i] = rev[i >> 1] >> 1;
    
            if (i & 1)
                rev[i] |= len >> 1;
        }
    
        fft(_x1, 1);
        fft(_x2, 1);
    
        for (int i = 0; i < len; ++i)
            _x1[i] = _x1[i] * _x2[i];
    
        fft(_x1, -1);
    
        for (int i = 0; i < len; ++i)
            ans[i] = int(_x1[i].x + 0.5);
    
        for (int i = 0; i <= n + m; ++i)
            printf("%d ", ans[i]);
    }
    
    • 1

    信息

    ID
    5539
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者