#46288: C++ AC (0.7s, 50.7MB)


1121228@stu.wghs.tp.edu.tw (你知道我是誰嗎!!??)

學校 : 臺北市私立薇閣高級中學
編號 : 266561
來源 : [60.248.154.139]
最後登入時間 :
2025-08-21 12:45:57

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int G = 3;

using VI = vector<int>;

int fastpow(int a, int b, int m = MOD) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % m;
        a = 1LL * a * a % m;
        b >>= 1;
    }
    return res;
}

void ntt(vector<int>& a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wlen = fastpow(G, (MOD - 1) / len);
        if (invert) wlen = fastpow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; ++j) {
                int u = a[i + j], v = 1LL * a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = 1LL * w * wlen % MOD;
            }
        }
    }

    if (invert) {
        int inv_n = fastpow(n, MOD - 2);
        for (int& x : a)
            x = 1LL * x * inv_n % MOD;
    }
}

VI parse(const string& s) {
    VI v;
    for (char c : s)
        v.push_back(c - '0');
    reverse(v.begin(), v.end());
    return v;
}

VI add(VI a, VI b) {
    VI res;
    int carry = 0;
    for (int i = 0; i < max(a.size(), b.size()) || carry; i++) {
        if (i == a.size()) a.push_back(0);
        int val = a[i] + (i < b.size() ? b[i] : 0) + carry;
        res.push_back(val % 10);
        carry = val / 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

VI sub(VI a, VI b) {
    // assume a >= b
    VI res;
    int carry = 0;
    for (int i = 0; i < a.size(); i++) {
        int val = a[i] - (i < b.size() ? b[i] : 0) - carry;
        if (val < 0) val += 10, carry = 1;
        else carry = 0;
        res.push_back(val);
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

VI multiply(VI a, VI b) {
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++)
        a[i] = 1LL * a[i] * b[i] % MOD;
    ntt(a, true);

    VI res(n);
    int carry = 0;
    for (int i = 0; i < n; i++) {
        long long cur = a[i] + carry;
        res[i] = cur % 10;
        carry = cur / 10;
    }
    while (carry) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

void print(VI v) {
    for (int d : v) cout << d;
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string A, B, op;
    cin >> A >> op >> B;

    auto a = parse(A);
    auto b = parse(B);
    if (op == "+") {
        print(add(a, b));
    } else if (op == "-") {
        if (A == B) {
            cout << 0 << '\n';
        } else {
            // a > b assumed
            print(sub(a, b));
        }
    } else if (op == "*") {
        print(multiply(a, b));
    }
    return 0;
}

#46290: Re: C++ AC (0.7s, 50.7MB)


1121228@stu.wghs.tp.edu.tw (你知道我是誰嗎!!??)

學校 : 臺北市私立薇閣高級中學
編號 : 266561
來源 : [60.248.154.139]
最後登入時間 :
2025-08-21 12:45:57

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int G = 3;

using VI = vector<int>;

int fastpow(int a, int b) {
    int res = 1;
    int base = a;
    while (b) {
        if (b & 1) res = (int)((int64_t)res * base % MOD);
        base = (int)((int64_t)base * base % MOD);
        b >>= 1;
    }
    return res;
}

void ntt(VI &a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wlen = fastpow(G, (MOD - 1) / len);
        if (invert) wlen = fastpow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; ++j) {
                int u = a[i + j];
                int v = (int)((int64_t)a[i + j + half] * w % MOD);
                a[i + j] = u + v < MOD ? u + v : u + v - MOD;
                a[i + j + half] = u - v >= 0 ? u - v : u - v + MOD;
                w = (int)((int64_t)w * wlen % MOD);
            }
        }
    }

    if (invert) {
        int inv_n = fastpow(n, MOD - 2);
        for (int &x : a)
            x = (int)((int64_t)x * inv_n % MOD);
    }
}

VI parse(const string &s) {
    VI v(s.size());
    for (int i = 0; i < (int)s.size(); i++)
        v[(int)s.size() - 1 - i] = s[i] - '0';  // 反轉放好,後續不用再反轉
    return v;
}

VI add(const VI &a, const VI &b) {
    int n = (int)max(a.size(), b.size());
    VI res;
    res.reserve(n + 1);
    int carry = 0;
    for (int i = 0; i < n || carry; ++i) {
        int x = carry;
        if (i < (int)a.size()) x += a[i];
        if (i < (int)b.size()) x += b[i];
        carry = x / 10;
        res.push_back(x % 10);
    }
    // 去除末尾多餘0
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

VI sub(const VI &a, const VI &b) {
    // 假設 a >= b
    VI res;
    res.reserve(a.size());
    int carry = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        int x = a[i] - carry - (i < (int)b.size() ? b[i] : 0);
        if (x < 0) x += 10, carry = 1;
        else carry = 0;
        res.push_back(x);
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

VI multiply(VI a, VI b) {
    int n = 1;
    while (n < (int)(a.size() + b.size()))
        n <<= 1;
    a.resize(n);
    b.resize(n);

    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++)
        a[i] = (int)((int64_t)a[i] * b[i] % MOD);
    ntt(a, true);

    VI res;
    res.reserve(n);
    int64_t carry = 0;
    for (int i = 0; i < n; i++) {
        int64_t cur = a[i] + carry;
        res.push_back(int(cur % 10));
        carry = cur / 10;
    }
    while (carry > 0) {
        res.push_back(int(carry % 10));
        carry /= 10;
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

void print(const VI &v) {
    for (int i = (int)v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B, op;
    cin >> A >> op >> B;

    VI a = parse(A), b = parse(B);

    if (op == "+") {
        print(add(a, b));
    } else if (op == "-") {
        if (A == B) {
            cout << 0 << '\n';
        } else {
            print(sub(a, b)); // 假設 A >= B
        }
    } else if (op == "*") {
        print(multiply(a, b));
    }
    return 0;
}

AC (0.7s, 43.4MB) 
CPP
#46291: Re: C++ AC (0.7s, 50.7MB)


321qwedsa000@gmail.com (灝)

學校 : 國立臺北商業大學
編號 : 70186
來源 : [114.32.102.214]
最後登入時間 :
2025-06-13 14:55:54

#include <cstdio>       // For scanf, printf
#include <string>       // For std::string, std::to_string
#include <vector>       // For std::vector
#include <algorithm>    // For std::reverse, std::swap
#include <cmath>        // For std::acos, std::sin, std::cos, std::round
#include <complex>      // For std::complex (use with long double)
#include <cstring>      // For strlen
#include <iostream>     // For std::ios_base, std::cin, std::tie

// Helper: Removes leading zeros from a string, handles "0" correctly
std::string removeLeadingZeros(std::string s) {
    s.erase(0, s.find_first_not_of('0'));
    return s.empty() ? "0" : s;
}

// Adds two large numbers (string representation)
std::string Add(std::string a, std::string b) {
    if (a.length() < b.length()) std::swap(a, b); // Ensure 'a' is longer
    std::string res = "";
    int carry = 0;
    for (int i = 0; i < a.length(); ++i) {
        int sum = (a[a.length() - 1 - i] - '0') + carry;
        if (i < b.length()) sum += (b[b.length() - 1 - i] - '0');
        res += (sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry) res += (carry + '0');
    std::reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

// Subtracts two large numbers (string representation)
std::string Sub(std::string a, std::string b) {
    bool neg = false;
    if (a.length() < b.length() || (a.length() == b.length() && a < b)) {
        neg = true;
        std::swap(a, b);
    }
    if (a == b) return "0";

    std::string res = "";
    int borrow = 0;
    for (int i = 0; i < a.length(); ++i) {
        int diff = (a[a.length() - 1 - i] - '0') - borrow;
        if (i < b.length()) diff -= (b[b.length() - 1 - i] - '0');
        if (diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; }
        res += (diff + '0');
    }
    std::reverse(res.begin(), res.end());
    return (neg ? "-" : "") + removeLeadingZeros(res);
}

// Constant for PI, now using long double for higher precision
const long double PI = std::acos(-1.0L); // Use -1.0L for long double argument

// Fast Fourier Transform (FFT) function - now using long double
void fft(std::vector<std::complex<long double>>& a, bool invert) { // Changed template parameter to long double
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit;
        if (i < j) std::swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        long double ang = 2 * PI / len * (invert ? -1 : 1); // Angle in long double
        std::complex<long double> wlen(std::cos(ang), std::sin(ang)); // Complex numbers with long double
        for (int i = 0; i < n; i += len) {
            std::complex<long double> w(1); // Complex number with long double
            for (int j = 0; j < len / 2; j++) {
                std::complex<long double> u = a[i + j], v = a[i + j + len / 2] * w; // Complex operations
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) for (auto& x : a) x /= n;
}

// Multiplies two large numbers using FFT, returns string
std::string multiply_fft(const char* a_str, const char* b_str) {
    // Define the base and how many decimal digits it represents
    const int BASE = 10000; // Using base 10^4
    const int POWER = 4;    // Each FFT element represents 4 decimal digits

    int na_len = std::strlen(a_str);
    int nb_len = std::strlen(b_str);

    std::vector<std::complex<long double>> fa, fb; // Changed vector element type to long double

    // Convert string to vector of numbers in the chosen base (reverse order)
    for (int i = na_len - 1; i >= 0; ) {
        long long chunk = 0;
        long long p10 = 1;
        for (int j = 0; j < POWER && i >= 0; ++j) {
            chunk += (a_str[i--] - '0') * p10;
            p10 *= 10;
        }
        fa.push_back(static_cast<long double>(chunk)); // Cast chunk to long double
    }
    for (int i = nb_len - 1; i >= 0; ) {
        long long chunk = 0;
        long long p10 = 1;
        for (int j = 0; j < POWER && i >= 0; ++j) {
            chunk += (b_str[i--] - '0') * p10;
            p10 *= 10;
        }
        fb.push_back(static_cast<long double>(chunk)); // Cast chunk to long double
    }

    // Determine FFT size
    int fn = 1;
    while (fn < fa.size() + fb.size() - 1) fn <<= 1; // Minimum length for product polynomial
    fa.resize(fn); fb.resize(fn);

    // Perform FFT on both coefficient vectors
    fft(fa, false);
    fft(fb, false);

    // Multiply transformed polynomials element-wise
    for (int i = 0; i < fn; ++i) fa[i] *= fb[i];

    // Perform inverse FFT
    fft(fa, true);

    // Extract results and handle carries in the new base
    std::vector<long long> res_digits; // No initial size, will resize as needed
    long long carry = 0;
    // Iterate until all coefficients are processed AND there is no more carry
    for (int i = 0; i < fn || carry; ++i) {
        // If current index goes beyond fa's original range (fn), then fa[i] is 0,
        // so current_val just consists of the carry
        long long current_val = (i < fn ? static_cast<long long>(std::round(fa[i].real())) : 0) + carry;
        
        // Ensure res_digits can hold the current index. Resize grows only if necessary.
        if (i >= res_digits.size()) {
             res_digits.resize(i + 1);
        }
        
        res_digits[i] = current_val % BASE; // Current digit is current_val % BASE
        carry = current_val / BASE;         // Carry is current_val / BASE
    }

    // Remove leading zero chunks (from the most significant end)
    // Only remove if more than one chunk and the last one is 0. This ensures "0" itself is not trimmed.
    while (res_digits.size() > 1 && res_digits.back() == 0) {
        res_digits.pop_back();
    }

    // Convert the result from the chosen base back to a decimal string
    std::string result_str = "";
    // Append the most significant chunk first
    result_str += std::to_string(res_digits.back());
    // Append remaining chunks, padding with leading zeros if necessary
    for (int i = res_digits.size() - 2; i >= 0; --i) {
        // Convert chunk to string
        std::string s_chunk = std::to_string(res_digits[i]);
        // Pad with leading zeros to POWER digits (e.g., "0078" for 78 if POWER=4)
        result_str += std::string(POWER - s_chunk.length(), '0') + s_chunk;
    }
    
    return removeLeadingZeros(result_str); // Final cleanup for any overall leading zeros (e.g. from BASE logic or `to_string` for single '0' number)
}

char a_str_input[1000002];
char b_str_input[1000002];

int main() {
    // Optimize C++ standard streams for competitive programming (though scanf/printf are used here)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); // This line requires #include <iostream>

    char op;
    // Read the two numbers and the operator. Cast to void to suppress -Wunused-result warning.
    (void)scanf("%s %c %s", a_str_input, &op, b_str_input);

    std::string answer;
    switch (op) {
        case '+': answer = Add(std::string(a_str_input), std::string(b_str_input)); break;
        case '-': answer = Sub(std::string(a_str_input), std::string(b_str_input)); break;
        case '*': answer = multiply_fft(a_str_input, b_str_input); break;
        default:
            fprintf(stderr, "Error: Unknown operator '%c'\n", op);
            return 1;
    }
    printf("%s\n", answer.c_str());

    return 0;
}
大佬我的程式哪邊還能優化?