#46294: c++ AC (0.4s,47.5MB)


321qwedsa000@gmail.com (灝)

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

#include <cstdio>       // For scanf, printf, strlen
#include <string>       // For std::string, std::to_string
#include <vector>       // For std::vector
#include <algorithm>    // For std::reverse, std::swap, std::max
#include <iostream>     // For std::ios_base, std::cin, std::tie

// 常量用於NTT: MOD為質數,G為原根。
// 998244353是常見的NTT模數,因為它是一個質數,且 (MOD - 1) 包含足夠大的 2 的冪因子 (2^23)。
const int MOD = 998244353;
const int G = 3; // 3 是 998244353 的一個原根。

// 模冪運算 (a^b % MOD)
int fastpow(int a, int b) {
    int res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = (int)((long long)res * a % MOD);
        a = (int)((long long)a * a % MOD);
        b >>= 1;
    }
    return res;
}

// 數論變換 (NTT)
// a: 係數向量
// invert: true 為逆變換 (IDFT/INTT),false 為正變換 (DFT/NTT)
void ntt(std::vector<int> &a, bool invert) {
    int n = (int)a.size();

    // 重新排序位數 (bit-reversal permutation)
    // 使得之後的蝴蝶操作能在正確位置上執行
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        // Fix: Should be bit >>= 1, not bit >>= 0
        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) {
        // 計算原根 wlen,對於正變換使用 G,對於逆變換使用 G 的模逆元
        int wlen = fastpow(G, (MOD - 1) / len);
        if (invert) wlen = fastpow(wlen, MOD - 2); // wlen的模逆元 (費馬小定理: a^(MOD-2) = a^-1 mod MOD)

        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)((long long)a[i + j + half] * w % MOD); // 下半部分乘上 w

                a[i + j] = u + v; // 相加
                if (a[i + j] >= MOD) a[i + j] -= MOD;

                a[i + j + half] = u - v; // 相減
                if (a[i + j + half] < 0) a[i + j + half] += MOD;
                
                w = (int)((long long)w * wlen % MOD); // 更新 w
            }
        }
    }

    // 逆變換結束後,需要將結果除以 n (乘上 n 的模逆元)
    if (invert) {
        int inv_n = fastpow(n, MOD - 2); // n的模逆元
        for (int &x : a)
            x = (int)((long long)x * inv_n % MOD);
    }
}

// 將數字字串解析成數字向量 (reverse order: 低位在前)
std::vector<int> parse(const std::string &s) {
    std::vector<int> v(s.length());
    for (int i = 0; i < (int)s.length(); ++i) {
        v[i] = s[s.length() - 1 - i] - '0'; // 低位到高位
    }
    return v;
}

// 從數字向量轉換回字串 (同時去除前導零)
std::string vectorToString(const std::vector<int> &v) {
    if (v.empty()) return "0"; // Handle empty vector
    
    int i = (int)v.size() - 1;
    while (i > 0 && v[i] == 0) i--; // 跳過高位多餘的0 (從右邊往左邊)

    std::string s = "";
    s.reserve(i + 1); // Pre-allocate string for efficiency
    for (; i >= 0; i--) {
        s += (v[i] + '0');
    }
    return s.empty() ? "0" : s; // 如果字符串仍然为空(如输入是"0"),則返回"0"
}


// 加法運算
std::vector<int> add(const std::vector<int> &a, const std::vector<int> &b) {
    int n = (int)std::max(a.size(), b.size());
    std::vector<int> 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];
        
        res.push_back(x % 10);
        carry = x / 10;
    }
    return res; // 低位在前,vectorToString 會處理顯示
}

// 比較兩個數的大小 (字串形式),sa < sb 返回 true
bool isSmaller(const std::string& sa, const std::string& sb) {
    if (sa.length() != sb.length()) {
        return sa.length() < sb.length();
    }
    return sa < sb; // 相同長度時直接比較字串 (字典序)
}

// 減法運算 (確保第一個參數的數值大於或等於第二個參數)
std::vector<int> subtract_non_negative(const std::vector<int> &a, const std::vector<int> &b) {
    std::vector<int> res;
    res.reserve(a.size()); // 預留空間
    int borrow = 0;
    for (int i = 0; i < (int)a.size(); ++i) {
        int x = a[i] - borrow - (i < (int)b.size() ? b[i] : 0);
        if (x < 0) {
            x += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(x);
    }
    // 返回結果時,會保留所有的0,vectorToString會處理顯示前導零。
    return res;
}

// 乘法運算
std::vector<int> multiply(std::vector<int> a, std::vector<int> b) {
    // 找出 NTT 運算所需的最小 2 的冪次大小 n
    // n 必須大於等於 (a的位數 + b的位數 - 1),因為結果多項式 degree is deg(A) + deg(B)
    int n = 1;
    // (a.size() + b.size() - 1) 代表結果多項式的最大項數
    while (n < (int)(a.size() + b.size() - 1))
        n <<= 1;
    
    a.resize(n, 0); // 擴展到 n 位並補0
    b.resize(n, 0); // 擴展到 n 位並補0

    // 對 a 和 b 執行 NTT
    ntt(a, false);
    ntt(b, false);

    // 在頻域 (DFT) 進行點乘
    for (int i = 0; i < n; i++)
        a[i] = (int)((long long)a[i] * b[i] % MOD);

    // 對結果執行逆 NTT,將頻域轉回時域
    ntt(a, true);

    std::vector<int> res;
    // 結果的長度最多為輸入長度之和 + 1 (考慮進位)
    res.reserve(a.size() + b.size() + 2); // 稍微多一些的預留空間

    long long carry = 0; // 進位
    // 循環處理所有可能的結果位元和進位
    for (int i = 0; i < n || carry; i++) { 
        long long current_val = (i < n ? a[i] : 0) + carry; // 當前位的值加上進位 (如果超過n則取0)
        res.push_back(int(current_val % 10)); // 當前位的實際數字
        carry = current_val / 10;             // 計算新的進位
    }
    return res; // 返回的vector是低位在前,vectorToString會處理顯示
}


char A_str_input[1000002]; // 輸入 A 的字元陣列
char B_str_input[1000002]; // 輸入 B 的字元陣列

int main() {
    // 加速 C++ 標準 I/O,這對於大型輸入很重要
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    char op_char;
    // 使用 scanf 讀取以保持與您原先程式碼輸入方式一致,並避免-Wunused-result警告
    (void)scanf("%s %c %s", A_str_input, &op_char, B_str_input);

    std::string A_str(A_str_input);
    std::string B_str(B_str_input);
    std::string op_str(1, op_char); // 將 char 轉為 string 便於比較

    std::vector<int> a_parsed = parse(A_str);
    std::vector<int> b_parsed = parse(B_str);
    
    std::vector<int> result_vec;

    if (op_str == "+") {
        result_vec = add(a_parsed, b_parsed);
    } else if (op_str == "-") {
        // 特殊處理 "0 - 0"
        if (A_str == "0" && B_str == "0") {
            printf("0\n");
            return 0;
        }
        if (A_str == B_str) {
            printf("0\n"); // 如果 A == B,直接輸出 0
            return 0;
        } else if (isSmaller(A_str, B_str)) {
            // 如果 A < B,結果為負數,先計算 B - A,然後加負號
            result_vec = subtract_non_negative(b_parsed, a_parsed);
            printf("-%s\n", vectorToString(result_vec).c_str());
            return 0; // 輸出完畢,程式結束
        } else {
            // 如果 A > B,直接計算 A - B
            result_vec = subtract_non_negative(a_parsed, b_parsed);
        }
    } else if (op_str == "*") {
        // 特殊處理乘以 0 的情況,避免不必要的NTT運算
        if (A_str == "0" || B_str == "0") {
            printf("0\n");
            return 0;
        }
        result_vec = multiply(a_parsed, b_parsed);
    }

    // 打印最終結果
    printf("%s\n", vectorToString(result_vec).c_str());

    return 0;