求救,错了一个点,不知道为什么
查看原帖
求救,错了一个点,不知道为什么
143303
晚晴楼主2023/4/15 23:45
#ifndef ONLINE_JUDGE
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<tuple>
#include<ctime>
#include<bitset>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<complex>
#else
#include<bits/stdc++.h>
#endif
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::stack;
using std::priority_queue;
using std::queue;
using std::map;
using std::set;
using std::multiset;
using std::list;
using std::pair;
using std::tuple;
using std::ostringstream;
using std::bitset;
using std::complex;
using std::abs;
using std::sqrt;
using std::ceil;
using std::floor;
using std::round;
using std::sin;
using std::cos;
using std::tan;
using std::asin;
using std::acos;
using std::atan;
using std::get;
using std::swap;
using std::sort;
using std::min;
using std::max;
using std::reverse;
using std::make_pair;
using std::greater;

int nTestCase, curTestCase;
ostringstream os;

void makedata() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "w", stdout);
#endif
    cout << 1000 << endl;
    srand(time(0));
    for (int i = 0; i < 1000; i++) {
        cout << "10 27" << endl;
        for (int j = 1; j < 10; j++) cout << rand() % j << ' ' << j << ' ' << rand() % 9 + 1 << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdout);
#endif
}
void TLE() {
    for (int i = 0;; i++) cout << (i % 1000000007 ? 1 : 2) << endl;
}
void MLE(string s = "") {
    MLE(s + ' ');
}
template <typename T> inline void check_memory(T& v, int n) {
    if (v.size() < n) v.resize(n);
}

void discrete_fourier_transform(vector<complex<double> >& a, int d, int f) {
    int n = 1 << d;
    assert(a.size() <= n);
    if (n != a.size()) {
        int t = a.size();
        a.resize(n);
        for (int i = t; i < n; i++) a[i] = { 0,0 };
    }
    vector<int> rev(n);
    for (int i = 0; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (d - 1));
    for (int i = 0; i < n; i++) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    double pi = acos(-1);
    for (int i = 1; i < n; i <<= 1) {
        auto wn = exp(complex<double>(0, f * pi / i));
        for (int j = 0; j < n; j += i << 1) {
            complex<double> w(1, 0);
            for (int k = j; k < j + i; k++) {
                complex<double> x = a[k], y = w * a[k + i];
                a[k] = x + y;
                a[k + i] = x - y;
                w *= wn;
            }
        }
    }
    if (f == -1) {
        for (int i = 0; i < n; i++) a[i] /= n;
    }
}



int main() {
    //makedata();
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0), cin.tie(0);

    nTestCase = 1;
    //cin >> nTestCase;


    for (curTestCase = 1; curTestCase <= nTestCase; curTestCase++) {
        string a, b;
        cin >> a >> b;
        vector<complex<double> > aa(a.size()), bb(b.size());
        for (int i = 0; i < a.size(); i++) aa[i] = { double(a[a.size() - i - 1] - '0'),0 };
        for (int i = 0; i < b.size(); i++) bb[i] = { double(b[b.size() - i - 1] - '0'),0 };
        int d = 0;
        while ((1 << d) < (aa.size() + bb.size())) d++;
        discrete_fourier_transform(aa, d, 1);
        discrete_fourier_transform(bb, d, 1);
        for (int i = 0; i < (1 << d); i++) aa[i] *= bb[i];
        discrete_fourier_transform(aa, d, -1);
        vector<int> aaa(aa.size(), 0);
        for (int i = 0; i < aaa.size(); i++) {
            aaa[i] += round(aa[i].real());
            if (aaa[i] > 10) aaa[i + 1] += aaa[i] / 10;
            aaa[i] %= 10;
        }
        while (aaa[aaa.size() - 1] == 0) aaa.pop_back();
        reverse(aaa.begin(), aaa.end());
        for (int i = 0; i < aaa.size(); i++) cout << aaa[i];
        cout << endl;
    }
    return 0;
}

2023/4/15 23:45
加载中...