思路与算法

按加减、乘法、幂、原子四层递归下降解析。每个表达式直接求得整系数向量，向量第k项是a^k系数。加减逐项处理，乘法做卷积，正整数幂用重复平方。幂这一层连续读取^指数并从左到右合并，使a^2^3等于(a^2)^3。去掉最高位0后，把各选项完整系数向量与题干比较，相同就输出对应字母。

正确性说明

整系数多项式在所有a上恒等，当且仅当各次幂系数逐项相等。对表达式结构归纳：常量与变量向量正确；加减的系数逐项相加减正确，乘法展开后同次幂系数恰为卷积，整数幂是反复乘法，故各语法节点都得到精确多项式。递归分层遵守题定优先级，同层循环遵守左结合。局部运算域保证所有所需低次幂和子式次数≤1000、系数≤10^15，卷积暂存最多1001项、各乘积≤10^30的和，其绝对值小于2^127，128位累加不会溢出。故向量比较是精确充要判定，不存在有限点代入或固定模数相等的漏判风险。

复杂度

设表达式最大长度E≤50，选项数n≤26，多项式最大次数D≤1000，指数e≤10。每次卷积含初始化为O(D²)，一次幂最多O(log e)次乘法，全部解析运算可界为O((n+1)E D² log(e+1))，读入与词法O((n+1)E)。递归临时向量空间O(E D)，卷积128位临时空间O(D)；本题有明确D与系数域。

易错点

^必须左结合，不能按常见语言习惯改成右结合。减法可产生负系数；零多项式需统一去掉尾0。不能把取模后的同值或若干整数代入相同当成恒等证明。原样例题干补左括号为(a+1)^2；本题执行公开写明的本地精确运算域。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using Poly = vector<long long>;
const long long LIMIT = 1000000000000000LL;
void trim(Poly &a) {
    while (a.size() > 1 && !a.back())
        a.pop_back();
}
Poly add(const Poly &a, const Poly &b, int sign) {
    Poly c(max(a.size(), b.size()));
    for (size_t i = 0; i < c.size(); i++) {
        __int128 x = (i < a.size() ? a[i] : 0) + (__int128)sign * (i < b.size() ? b[i] : 0);
        assert(x >= -LIMIT && x <= LIMIT);
        c[i] = (long long)x;
    }
    trim(c);
    return c;
}
Poly mul(const Poly &a, const Poly &b) {
    assert(a.size() + b.size() - 2 <= 1000);
    vector<__int128> raw(a.size() + b.size() - 1);
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < b.size(); j++)
            raw[i + j] += (__int128)a[i] * b[j];
    Poly c(raw.size());
    for (size_t i = 0; i < c.size(); i++) {
        assert(raw[i] >= -LIMIT && raw[i] <= LIMIT);
        c[i] = (long long)raw[i];
    }
    trim(c);
    return c;
}
Poly power(Poly a, int e) {
    Poly c(1, 1);
    while (e) {
        if (e & 1)
            c = mul(c, a);
        e >>= 1;
        if (e)
            a = mul(a, a);
    }
    return c;
}
struct Parser {
    string s;
    size_t at = 0;
    Parser(string text) {
        for (char c : text)
            if (c != ' ')
                s += c;
    }
    Poly atom() {
        if (s[at] == '(') {
            at++;
            Poly a = expr();
            assert(s[at++] == ')');
            return a;
        }
        if (s[at] == 'a') {
            at++;
            return Poly{0, 1};
        }
        int x = 0;
        while (at < s.size() && isdigit((unsigned char)s[at]))
            x = x * 10 + s[at++] - '0';
        assert(x >= 1 && x < 10000);
        return Poly(1, x);
    }
    Poly termpow() {
        Poly a = atom();
        while (at < s.size() && s[at] == '^') {
            at++;
            int e = 0;
            while (at < s.size() && isdigit((unsigned char)s[at]))
                e = e * 10 + s[at++] - '0';
            assert(1 <= e && e <= 10);
            a = power(a, e);
        }
        return a;
    }
    Poly term() {
        Poly a = termpow();
        while (at < s.size() && s[at] == '*') {
            at++;
            a = mul(a, termpow());
        }
        return a;
    }
    Poly expr() {
        Poly a = term();
        while (at < s.size() && (s[at] == '+' || s[at] == '-')) {
            int sign = s[at++] == '+' ? 1 : -1;
            a = add(a, term(), sign);
        }
        return a;
    }
    Poly parse() {
        Poly a = expr();
        assert(at == s.size());
        return a;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!getline(cin, s))
        return 0;
    Poly target = Parser(s).parse();
    int n;
    cin >> n;
    getline(cin, s);
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        if (Parser(s).parse() == target)
            cout << char('A' + i);
    }
    cout << '\n';
}