제출 #1187108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187108		JungPS	A + B (IOI24_aplusb)	C++20	0 / 100	0 ms	328 KiB

aplusb

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

void fft(vector<cd> &a, bool invert) {
    int n = a.size();
    if (n == 1) return;

    vector<cd> a0(n / 2), a1(n / 2);
    for (int i = 0; 2 * i < n; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }

    fft(a0, invert);
    fft(a1, invert);

    for (int i = 0; 2 * i < n; i++) {
        cd w = polar(1.0, 2 * PI * i / n * (invert ? -1 : 1));
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n / 2] /= 2;
        }
    }
}

vector<int> multiplyFFT(const vector<int> &a, const vector<int> &b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n); fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    long long carry = 0;
    for (int i = 0; i < n; i++) {
        long long val = (long long)(round(fa[i].real())) + carry;
        result[i] = val % 10;
        carry = val / 10;
    }

    while (carry) {
        result.push_back(carry % 10);
        carry /= 10;
    }

    while (result.size() > 1 && result.back() == 0) result.pop_back();
    return result;
}

vector<int> intToVector(int n) {
    if (n == 0) return {0};
    vector<int> res;
    while (n > 0) {
        res.push_back(n % 10);
        n /= 10;
    }
    return res;
}

int vectorToInt(const vector<int>& v) {
    int res = 0;
    for (int i = v.size() - 1; i >= 0; i--) {
        res = res * 10 + v[i];
    }
    return res;
}

int sum(int A, int B) {
    vector<int> a = intToVector(A);
    vector<int> b = intToVector(B);

    vector<int> oneA(a.size(), 1);
    vector<int> oneB(b.size(), 1);

    vector<int> addA = multiplyFFT(a, oneA);
    vector<int> addB = multiplyFFT(b, oneB);

    int n = max(addA.size(), addB.size());
    vector<int> result(n);
    int carry = 0;
    for (int i = 0; i < n; i++) {
        int d = (i < addA.size() ? addA[i] : 0) +
                (i < addB.size() ? addB[i] : 0) + carry;
        result[i] = d % 10;
        carry = d / 10;
    }
    if (carry) result.push_back(carry);

    return vectorToInt(result);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50