[NOIP2005-提高] 等价表达式

GitHub跳转原题关系图返回列表

把等价判断化为多点代入：递归下降求值器对 a=0..3 分别求值，四次取值全相等的选项即与题干恒等。

OJ: roj

题目 ID: 3543

难度:提高

标签:表达式解析递归下降数学python

创建: 2026-10-02 06:42

更新: 2026-10-10 11:30

形式化题目

给定一个关于变量 $a$ 的代数表达式 $E$ ，以及 $n$ （ $2 \leqslant n \leqslant 26$ ）个表达式 $E_1, \dots, E_n$ 。每个表达式由变量 a、小于 $10000$ 的正整数常量、运算符 + - * ^ 和括号组成，长度不超过 $50$ ，且可能含任意多的空格。运算优先级为 ^ $>$ * $>$ +/-，+ 与 - 同级，同优先级一律从左到右结合（包括 ^）；^ 的指数是 $1$ 到 $10$ 的正整数。

要求找出所有与 $E$ 恒等（对任意 $a$ 取值都相等）的 $E_i$ ，按字母序输出它们的标号 A, B, C, …（无分隔符）。数据保证至少存在一个等价选项。

正解

思路

朴素做法是把每个表达式按 $a$ 的幂展开成多项式，再逐项比较系数。但 ^ 的指数最高 $10$ ，乘方还能套乘方（如 $(a-6)^{10^{10}}$ ），展开后的系数动辄上百位，多项式乘法写起来又长又容易错。

为什么可以只代入几个点？ 判断恒等其实不需要完整的多项式：把 $E - E_i$ 看成一个关于 $a$ 的多项式 $f$ ，它是零多项式当且仅当处处取值为 $0$ 。反过来，只要 $f$ 不是零多项式，它的根就严格少于它的次数加一个。本题中表达式次数最高也就几十到一百量级，所以随便挑几个不同的 $a$ 值分别代入两边求值，四次取值全部相等才认定等价，就足以把数据里所有不恒等的式子对区分开——这就是"多点代入判定恒等"的思想。

剩下的只是对一个具体数值求表达式的值。用经典的递归下降，按优先级分四层文法，每层一个函数：

text

1
2
3
4expr  := term  ( (+|-) term )*      ← 加减层，从左到右累加
term  := power ( * power )*         ← 乘层，从左到右连乘
power := atom  ( ^ atom )*          ← 幂层，左结合！2^3^2 = 64
atom  := a | ( expr ) | 数字        ← 变量代入 x，括号递归回 expr

每层用 while 循环"吃掉"同优先级的后续运算符，天然实现左结合；a 直接返回代入值 $x$ 。空格在读入后统一删掉。Python 的大整数让 $(a-6)^{10^{10}}$ 这类天文数字也能精确求值，完全不需要担心溢出。

以样例 10 + (1 - a) + (a + 8) - (9 - 8) 代入 $a=2$ 为例，求值过程就是一棵自底向上折叠的表达式树：

层	片段	计算过程	结果
atom	`a`	代入 $x=2$	$2$
expr	`(1 - a)`	$1-2$	$-1$
expr	`(a + 8)`	$2+8$	$10$
expr	`(9 - 8)`	$9-8$	$1$
expr	整体	$10+(-1)+10-1$	$18$

而选项 10+8 代入 $a=2$ 得 $18$ ，四次代入全对上，所以它和题干等价（样例输出 IJ）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string s;
int pos;

ll parse_expr(ll x);
ll parse_term(ll x);
ll parse_power(ll x);
ll parse_atom(ll x);

ll parse_expr(ll x) {
    ll value = parse_term(x);
    while (pos < (int)s.size() && (s[pos] == '+' || s[pos] == '-')) {
        char op = s[pos]; pos++;
        ll rhs = parse_term(x);
        value = (op == '+') ? value + rhs : value - rhs;
    }
    return value;
}

ll parse_term(ll x) {
    ll value = parse_power(x);
    while (pos < (int)s.size() && s[pos] == '*') {
        pos++;
        value *= parse_power(x);
    }
    return value;
}

ll parse_power(ll x) {
    ll value = parse_atom(x);
    while (pos < (int)s.size() && s[pos] == '^') {
        pos++;
        ll e = parse_atom(x);
        ll r = 1;
        for (ll i = 0; i < e; i++) r *= value;
        value = r;
    }
    return value;
}

ll parse_atom(ll x) {
    if (s[pos] == 'a') { pos++; return x; }
    if (s[pos] == '(') {
        pos++;
        ll v = parse_expr(x);
        pos++;  // 跳过 ')'
        return v;
    }
    ll num = 0;
    while (pos < (int)s.size() && isdigit((unsigned char)s[pos])) {
        num = num * 10 + (s[pos] - '0');
        pos++;
    }
    return num;
}

ll calc(const string& tokens, ll x) {
    s = tokens;
    // 去掉空格
    string clean;
    for (size_t i = 0; i < tokens.size(); i++)
        if (tokens[i] != ' ') clean.push_back(tokens[i]);
    s = clean;
    pos = 0;
    return parse_expr(x);
}

bool same(const string& expr, const string& other) {
    for (ll x = 0; x < 4; x++)
        if (calc(expr, x) != calc(other, x)) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> lines;
    string line;
    while (getline(cin, line)) {
        // 去掉末尾 \r
        if (!line.empty() && line.back() == '\r') line.pop_back();
        lines.push_back(line);
    }
    // 处理可能带空行；第一行是标准表达式
    int idx = 0;
    while (idx < (int)lines.size() && lines[idx].empty()) idx++;
    string std_expr = lines[idx];
    idx++;
    while (idx < (int)lines.size() && lines[idx].empty()) idx++;
    int n = 0;
    if (idx < (int)lines.size()) n = atoi(lines[idx].c_str());
    idx++;
    string out;
    for (int i = 0; i < n; i++) {
        while (idx < (int)lines.size() && lines[idx].empty()) idx++;
        if (idx >= (int)lines.size()) break;
        if (same(std_expr, lines[idx]))
            out.push_back((char)('A' + i));
        idx++;
    }
    cout << out << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:00
# update_at: 2026-10-02 07:00

import sys

OPS = "+-*^"  # 四个可判定的二元运算符（左结合）


def calc(tokens: str, x: int) -> int:
    """求表达式在 a = x 处的值：运算符优先级 ^ > * > +/-，同级从左到右。"""
    s = tokens.replace(" ", "")  # 消掉多余空格，词法就只剩数、a、括号、运算符
    pos = 0                      # 全局扫描位置

    def parse_expr() -> int:
        """加减层：把若干乘积项按从左到右的 +/- 累加。"""
        nonlocal pos
        value = parse_term()
        while pos < len(s) and s[pos] in "+-":
            op = s[pos]
            pos += 1
            rhs = parse_term()
            value = value + rhs if op == "+" else value - rhs
        return value

    def parse_term() -> int:
        """乘层：把若干幂按从左到右的 * 连乘。"""
        nonlocal pos
        value = parse_power()
        while pos < len(s) and s[pos] == "*":
            pos += 1
            value *= parse_power()
        return value

    def parse_power() -> int:
        """幂层：左结合的 ^，即 2^3^2 = (2^3)^2 = 64。"""
        nonlocal pos
        value = parse_atom()
        while pos < len(s) and s[pos] == "^":
            pos += 1
            value **= parse_atom()  # 指数 ≤ 10，快速幂都不需要
        return value

    def parse_atom() -> int:
        """原子：变量 a（代入 x）、括号子表达式或十进制数。"""
        nonlocal pos
        if s[pos] == "a":
            pos += 1
            return x
        if s[pos] == "(":
            pos += 1
            value = parse_expr()
            pos += 1  # 跳过配对的 ')'
            return value
        start = pos
        while pos < len(s) and s[pos].isdigit():
            pos += 1
        return int(s[start:pos])

    return parse_expr()


def same(expr: str, other: str) -> bool:
    """两式在 0,1,2,3 处取值都相同才认定等价（4 次多项式差异即可被识破）。"""
    return all(calc(expr, x) == calc(other, x) for x in range(4))


def solve() -> None:
    lines = sys.stdin.read().splitlines()
    std = lines[0]
    n = int(lines[1])
    picks = [chr(ord("A") + i) for i in range(n) if same(std, lines[2 + i])]
    print("".join(picks))


if __name__ == "__main__":
    solve()

复杂度

设表达式长度上界 $L=50$ 。单次求值时每个字符只被扫描一次，为 $O(L)$ ；每个选项代入 $4$ 个点，共 $n+1 \leqslant 27$ 个表达式，总计算量约 $27 \times 4 \times 50 = 5400$ 次字符操作，远低于 $1\text{s}$ 限制。空间为递归深度 $O(L)$ 。

总结

判断两个含变量表达式是否恒等，不必展开成多项式：挑 $4$ 个不同的 $a$ 值代入，两边取值都相等即可认定等价（不同多项式的公共根个数小于次数）。
求值用递归下降四层文法 expr → term → power → atom；^ 是左结合的（2^3^2 = 64），这是本题最容易踩的坑。
Python 的精确大整数让最高达 $10^{210}$ 量级的中间结果无需取模；同样的算法在 C++ 中需要对大质数取模实现。

图示解析

递归下降的分层消化

以 (a + 1 + 5) * a ^ 2 代入 $a = 3$ 为例，展示四层函数如何接力：

text

1
2
3
4
5
6
7expr  ──► term ──► term ──► power ──► atom ──► ( expr )     ┐
   │                                   │                   │ 括号内重新
   │                                   │                   ▼ 从 expr 开始
   │                                   │            a+1+5 = 3+1+5 = 9
   │                                   ◄── 9 ^ atom = 9 ^ 2 = 81
   │            ◄── 9 * 81 = 729  （乘层从左到右连乘）
   └──► 729

观察重点：atom 遇到 ( 时重新从 expr 层进入，括号内算完返回，外层的 power 再继续处理 ^ 2。乘层在两个幂 $9$ 和 $81$ 都备好后连乘——每层只关心自己优先级的运算符，优先级高的自然先算完。