题解 | 牛牛的括号式

#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 10007;

int main() {
    string s;
    cin >> s;
    vector<int> a; // 存取每个括号中的常数

    // 分析每个括号内的常数，包括其符号
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            i++;
            int sign = (s[i + 1] == '+') ? 1 : -1;

            int num = 0;
            for (int j = i + 2; j < s.size() && s[j] != ')'; j++) {
                num = num * 10 + (s[j] - '0');
            }

            a.push_back(sign * num);
        }
    }

    int n = a.size();
    
    // 特殊情况：如果只有一个因子
    if (n == 1) {
        int result = (a[0] % MOD + MOD) % MOD;
        cout << result << endl;
        return 0;
    }

    // 使用前缀积和后缀积的方法
    vector<int> prefix(n + 1, 1); // 前缀积
    vector<int> suffix(n + 1, 1); // 后缀积
    
    // 计算前缀积：prefix[i] = a[0] * a[1] * ... * a[i-1]
    for (int i = 0; i < n; i++) {
        int num_mod = (a[i] % MOD + MOD) % MOD; // 处理负数
        prefix[i + 1] = (prefix[i] * num_mod) % MOD;
    }
    
    // 计算后缀积：suffix[i] = a[i] * a[i+1] * ... * a[n-1]
    for (int i = n - 1; i >= 0; i--) {  // 注意：这里应该是 i--
        int num_mod = (a[i] % MOD + MOD) % MOD; // 处理负数
        suffix[i] = (suffix[i + 1] * num_mod) % MOD;
    }

    // 计算一次项系数
    int linear_coeff = 0;
    for (int i = 0; i < n; i++) {
        // 除了a[i]之外所有数的乘积 = prefix[i] * suffix[i+1]
        int product_without_i = (prefix[i] * suffix[i + 1]) % MOD;
        linear_coeff = (linear_coeff + product_without_i) % MOD;
    }

    // 处理负数结果
    linear_coeff = (linear_coeff % MOD + MOD) % MOD;
    cout << linear_coeff << endl;

    return 0;
}