题解：P1054 [NOIP2005 提高组] 等价表达式

algo_h · 2024-12-04 16:40:29 · 题解

基于多项式表示和递归下降表达式解析，判断表达式是否相等。多项式每项前的系数可能溢出 long（在评测机上为 64 bit 带符号整数），但可以在不对大质数取模的前提下通过本题。使用 int 表示多项式系数则不能通过最后一个测试点。严格的做法可以使用高精度整数。

详细解释见代码实现。

#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;
}