Submission #1188615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188615		peteza	Multiply (CEOI17_mul)	C++20	100 / 100	70 ms	8688 KiB

mul

#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
double pi = acos(-1);

int n, m;
vector<cd> va, vb;
string s;

void fft(vector<cd>&arr, bool mode) {
    int cn = arr.size();
    if(cn == 1) return;
    vector<cd> a0, a1;
    for(int i=0;i<cn;i+=2) {
        a0.push_back(arr[i]);
        a1.push_back(arr[i+1]);
    }
    fft(a0, mode); fft(a1, mode);
    double ang = (mode ? -1 : 1) * 2*pi/cn;
    cd croot(1), w(cos(ang), sin(ang));
    for(int i=0;i<cn/2;i++) {
        arr[i] = a0[i] + croot * a1[i];
        arr[i+cn/2] = a0[i] - croot * a1[i];
        croot *= w;
    }
    if(mode) for(auto &e:arr) e /= 2;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    va.resize(n);
    vb.resize(m);
    cin >> s; reverse(s.begin(), s.end());
    for(int i=0;i<n;i++) va[i] = s[i] - '0';
    cin >> s; reverse(s.begin(), s.end());
    for(int i=0;i<m;i++) vb[i] = s[i] - '0';
    if(n < m) {swap(n, m); swap(va, vb);}
    va.push_back(0);
    while(vb.size() < va.size()) vb.push_back(0);
    while(__builtin_popcount(va.size()) > 1) {va.push_back(0); vb.push_back(0);}
    va.push_back(0); vb.push_back(0);
    while(__builtin_popcount(va.size()) > 1) {va.push_back(0); vb.push_back(0);}
    fft(va, 0); fft(vb, 0);
    for(int i=0;i<va.size();i++) va[i] *= vb[i];
    fft(va, 1);
    vector<int> ans;
    int curcar = 0;
    for(auto &e:va) {
        curcar += round(e.real());
        ans.push_back(curcar%10);
        curcar /= 10;
    }
    while(!ans.empty() && ans.back() == 0) ans.pop_back();
    reverse(ans.begin(), ans.end());
    for(auto &e:ans) cout << e;
    if(ans.empty()) cout << 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30