#include <iostream> #include <vector> using namespace std; // 几种特殊的分词类型 #define TOK_END (0x000) #define TOK_INT (0x101) #define TOK_VAR (0x102) struct Token { int type; int value; // type 为 TOK_INT 时存值 }; // 对表达式进行分词 vector<Token> tokenize(const string &expr) { vector<Token> tokens; size_t pos = 0; while (pos != expr.size()) { while (pos != expr.size() && isspace(expr[pos])) ++pos; // 跳过空白 if (pos == expr.size()) break; if (isdigit(expr[pos])) { // TOK_INT size_t beg = pos; while (pos != expr.size() && isdigit(expr[pos])) ++pos; tokens.push_back({TOK_INT, stoi(expr.substr(beg, pos - beg))}); } else if (expr[pos] == 'a') { // TOK_VAR tokens.push_back({TOK_VAR, 0}); ++pos; } else if ("+-*^()"s.find(expr[pos]) != string::npos) { // 标点符号 tokens.push_back({expr[pos], 0}); ++pos; } else { throw runtime_error("unexpected character: "s + expr[pos]); } } tokens.push_back({TOK_END, 0}); // 哨兵 return tokens; } // 我们根据本题中（一元）多项式运算的封闭性，选取多项式为唯一的操作数 struct Polynomial { vector<long> c; Polynomial &to(int power); // 乘方 Polynomial &mul(const Polynomial &); Polynomial &add(const Polynomial &); Polynomial &sub(const Polynomial &); Polynomial &regularize(); // 去除高位 0，方便比较 bool eq(const Polynomial &) const; // 判等 }; // 用快速幂计算多项式的乘方 Polynomial &Polynomial::to(int power) { Polynomial p = {{1}}, q = *this; while (power) { if (power & 1) p.mul(q); q.mul(q); power >>= 1; } return *this = p.regularize(); } // 多项式乘法，对应卷积 Polynomial &Polynomial::mul(const Polynomial &q) { if (c.empty() || q.c.empty()) return *this = {}; Polynomial p; p.c.resize(c.size() + q.c.size()); for (size_t i = 0; i < c.size(); ++i) { for (size_t j = 0; j < q.c.size(); ++j) p.c[i + j] += c[i] * q.c[j]; } return *this = p.regularize(); } // 多项式加法，低位对齐后每项前系数相加 Polynomial &Polynomial::add(const Polynomial &q) { if (c.size() < q.c.size()) c.resize(q.c.size()); for (size_t i = 0; i < q.c.size(); ++i) c[i] += q.c[i]; return this->regularize(); } // 多项式减法，类似加法 Polynomial &Polynomial::sub(const Polynomial &q) { if (c.size() < q.c.size()) c.resize(q.c.size()); for (size_t i = 0; i < q.c.size(); ++i) c[i] -= q.c[i]; return this->regularize(); } // 通过去除前导 0 实现表示唯一化 Polynomial &Polynomial::regularize() { while (!c.empty() && c.back() == 0) c.pop_back(); return *this; } // 递归下降解析表达式，优先级递增，左结合 Polynomial expr(Token *&token); Polynomial term(Token *&token); Polynomial factor(Token *&token); Polynomial base(Token *&token); // expr -> term { ('+' | '-') term } Polynomial expr(Token *&token) { Polynomial poly = term(token); while (token->type == '+' || token->type == '-') { int type = token->type; ++token; Polynomial poly2 = term(token); type == '+' ? poly.add(poly2) : poly.sub(poly2); } return poly; } // term -> factor { '*' factor } Polynomial term(Token *&token) { Polynomial poly = factor(token); while (token->type == '*') { ++token; Polynomial poly2 = factor(token); poly.mul(poly2); } return poly; } // factor -> base { '^' base } Polynomial factor(Token *&token) { Polynomial poly = base(token); while (token->type == '^') { ++token; Polynomial power = base(token); if (power.c.size() != 1) throw runtime_error("unexpected power order: " + to_string(power.c.size())); poly.to(power.c[0]); } return poly; } // base -> INT | VAR | '(' expr ')' Polynomial base(Token *&token) { if (token->type == TOK_INT) { int value = token->value; ++token; return {{value}}; } if (token->type == TOK_VAR) { ++token; return {{0, 1}}; } if (token->type == '(') { ++token; Polynomial poly = expr(token); if (token->type != ')') throw runtime_error("unmatched parenthesis"); ++token; return poly; } throw runtime_error("unexpected token type: " + to_string(token->type)); } // 在 regular 表示下，多项式相等当且仅当系数向量相等 bool Polynomial::eq(const Polynomial &q) const { return c == q.c; } // 读入一行输入，解析为多项式表示 Polynomial getexpr() { string line; getline(cin, line); vector<Token> tokens = tokenize(line); // for(const Token &token : tokens) { // cout << "type="; // if(token.type < 0x100) { // cout << "'" << char(token.type) << "'"; // } else { // cout << token.type; // } // cout << " value=" << token.value << endl; // } Token *p = tokens.data(); Polynomial poly = expr(p); if (p->type != TOK_END) throw runtime_error("trailing token of type: " + to_string(p->type)); // for(int c : poly.c) cout << " " << c; // cout << endl; return poly; } int main() { Polynomial poly = getexpr(); int n; cin >> n; string s; getline(cin, s); // 去除 n 后的换行 for (int i = 0; i < n; ++i) { try { Polynomial poly2 = getexpr(); if (poly2.eq(poly)) cout.put('A' + i); } catch (runtime_error &) { // Just skip it. } } cout << endl; return 0; }