样例没过,有负数,玄关求调
查看原帖
样例没过,有负数,玄关求调
992367
liserver楼主2024/7/23 13:44
#include <bits/stdc++.h>

const int MAXN = 4000000;
const double PI = 3.1415926535;

class complex
{
public:
    double a, b;

    complex() = default;
    complex(double _a, double _b) : a(_a), b(_b) {}

    complex operator+(complex other)
    {
        return complex(a + other.a, b + other.b);
    }

    complex operator-(complex other)
    {
        return complex(a - other.a, b - other.b);
    }

    complex operator*(complex other)
    {
        return complex(a * other.a - b * other.b, a * other.b + other.a * b);
    }

    void operator+=(complex other)
    {
        *this = *this + other;
    }

    void operator-=(complex other)
    {
        *this = *this - other;
    }

    void operator*=(complex other)
    {
        *this = *this * other;
    }
};

complex a[MAXN], b[MAXN];
int ans[MAXN];

void change(complex y[], int len)
{
    int i, j, k;

    for (int i = 1, j = len / 2; i < len - 1; i++)
    {
        if (i < j)
            std::swap(y[i], y[j]);

        k = len / 2;

        while (j >= k)
        {
            j = j - k;
            k = k / 2;
        }

        if (j < k)
            j += k;
    }
}

void FFT(complex arr[], int len, int flag)
{
    change(arr, len);

    // s 是合并的层数
    for (int s = 2; s <= len; s <<= 1)
    {
        // 单位根
        complex wn = complex(std::cos(2 * PI / s), flag * std::sin(2 * PI / s));

        // pos 是合并的位置
        for (int pos = 0; pos < len; pos += s)
        {
            // 遍历时的单位根
            complex w = complex(1, 0);

            // 遍历左半部分 右半部分O(1)求出
            for (int k = pos; k < pos + s / 2; k++)
            {
                // 蝴蝶变换
                complex ak = arr[k];
                complex t = arr[k + s / 2] * w;
                a[k] = ak + t;
                a[k + s / 2] = ak - t;
                w = w * wn;
            }
        }
    }

    if (flag == -1)
    {
        for (int i = 0; i < len; i++)
        {
            arr[i].a /= len;
        }
    }
}

int main()
{
    // IO优化
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::string stra, strb;
    std::cin >> stra >> strb;

    const int lena = stra.size(), lenb = strb.size();

    for (int i = 0; i < lena; i++)
    {
        a[i] = complex(stra[lena - 1 - i] - '0', 0);
    }

    for (int i = 0; i < lenb; i++)
    {
        b[i] = complex(strb[lenb - 1 - i] - '0', 0);
    }

    int y = 1;

    while (y < 2 * lena || y < 2 * lenb)
    {
        y <<= 1;
    }

    for (int i = lena; i <= y; i++)
    {
        a[i] = complex(0, 0);
    }

    for (int i = lenb; i <= y; i++)
    {
        b[i] = complex(0, 0);
    }

    FFT(a, y, 1);
    FFT(b, y, 1);

    for (int i = 0; i < y; i++)
    {
        a[i] *= b[i];
        ans[i] = 0;
    }

    FFT(a, y, -1);

    for (int i = 0; i < y; i++)
    {
        // 此处+0.5然后取整相当于四舍五入
        ans[i] += (int)(a[i].a + 0.5);
        // 进位
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }

    int h = lena + lenb + 2;

    while (ans[h] == 0 && h >= 0)
    {
        h--;
    }

    if (h == -1)
    {
        std::cout << 0;
    }

    else for (; h >= 0; h--)
    {
        std::cout << ans[h];
    }
}
2024/7/23 13:44
加载中...