算法
(栈,表达式求值,同余) $O(KNL)$
直接对表达式进行代数化简的难度系数太高,所以我们退而求其次,来验证两个表达式相等的必要条件:
如果两个表达式 $f(a)$ 和 $g(a)$ 等价,且表达式中不包含除法,那么对于任意整数 $a$,以及正整数 $p$,均会有 $f(a) \equiv g(a) \; mod \; p$。
剩下的问题就是当给定一个具体的 $a$ 时,如何计算表达式对 $p$ 的余数。这是经典的表达式求值问题,做法有很多种,这里给出一种比较常用的基于栈和运算符优先级的做法:
准备两个栈: stack<char> op
用来存储运算符,包括(, ), +, -, *, ^
; stack<int> num
用来存储被操作的数值。
运算的优先级是 '+' = '-' < '*' < '^'
。
从前往后依次考虑每个元素:
- 如果是数值,则直接插入
num
中; - 如果是操作符:
- 如果是
'('
则直接插入栈中; - 如果是
')'
则每次将op
栈顶的运算符取出并进行计算; - 如果是其他运算符,则比较当前运算符和
op
栈顶运算符的优先级,如果前者小于等于后者,则前者的运算符需要被先计算,否则两者的运算顺序未知,需要将当前运算符压入栈顶。
最终将栈中剩余运算符依次操作一遍即可。
时间复杂度
设表达式数量是 $N$,每个表达式的平均长度是 $L$,对于每对表达式测试 $K$ 个不同 $a$ 值。
表达式求值的时间复杂度是 $O(L)$,因此总时间复杂度是 $O(KNL)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
const int P = 13331;
map<char, int> priority;
stack<char> op;
stack<int> num;
void eval()
{
char c = op.top(); op.pop();
int b = num.top(); num.pop();
int a = num.top(); num.pop();
if (c == '+') num.push((a + b) % P);
else if (c == '-') num.push(((a - b) % P + P) % P);
else if (c == '*') num.push(a * b % P);
else
{
signed t = 1;
while (b -- ) t = t * a % P;
num.push(t);
}
}
int cal(string expr, int a)
{
op = stack<char>();
num = stack<int>();
for (int i = 0; i < expr.size(); i ++ )
{
if (expr[i] == ' ') continue;
if (expr[i] >= '0' && expr[i] <= '9')
{
int j = i, number = 0;
while (j < expr.size() && expr[j] >= '0' && expr[j] <= '9')
{
number = number * 10 + expr[j] - '0';
j ++ ;
}
i = j - 1;
num.push(number);
}
else if (expr[i] == 'a') num.push(a);
else
{
char c = expr[i];
if (c == '(') op.push(c);
else if (c != ')')
{
while (op.size() && priority[op.top()] >= priority[c]) eval();
op.push(c);
}
else
{
while (op.size() && op.top() != '(') eval();
op.pop();
}
}
}
while (op.size()) eval();
return num.top();
}
bool check(string expr1, string expr2)
{
for (int i = 0; i < 1000; i ++ )
if (cal(expr1, i) != cal(expr2, i))
return false;
return true;
}
int main()
{
char ops[] = "+-*^";
for (int i = 0; i < 5; i ++ ) priority[ops[i]] = i + 1;
priority['-'] = priority['+'];
string expr, line;
getline(cin, expr);
int n;
cin >> n;
getline(cin, line);
for (int i = 0; i < n; i ++ )
{
getline(cin, line);
if (check(expr, line)) cout << (char)('A' + i);
}
cout << endl;
return 0;
}
P=1e9+7呢?
也是可以的。
我用1e9+7 wa了,用13331就没事,为什么
炸了
####idx是什么?有用吗?
idx
这个变量没啥用,调试的时候写的,已删。减法那里为什么要变成正的数呢
C++里的取模是正数返回正余数,负数返回负余数,需要统一起来。
楼主你好,我在您的代码文本中发现了一点小错误,那就是在括号处理时,我们是将这个 ) 出现之前的所有运算符都清掉的,但是在括号内部出现的运算符,也就是 ) 之前的,我们是不是也应该加一个 op.top() != ‘(‘ 的条件呢,这里好像是错的
本题中指明了:表达式一定合法,所以如果遇到右括号,则这个while循环一定可以遇到一个与之相配的左括号,是没问题的。