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

题目描述

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

这个选择题中的每个表达式都满足下面的性质：

1. 表达式只可能包含一个变量 �a。
2. 表达式中出现的数都是正整数，而且都小于 1000010000。
3. 表达式中可以包括四种运算 ++（加），--（减），**（乘），^^（乘幂），以及小括号 ((，))。小括号的优先级最高，其次是 ^^，然后是 **，最后是 ++ 和 --。++ 和 -- 的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符 ++，--，**，^^ 以及小括号((，)) 都是英文字符）
4. 幂指数只可能是 11 到 1010 之间的正整数（包括 11 和 1010）。
5. 表达式内部，头部或者尾部都可能有一些多余的空格。

下面是一些合理的表达式的例子：

((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9………

输入格式

第一行给出的是题干中的表达式。

第二行是一个整数 �n，表示选项的个数。后面�n行，每行包括一个选项中的表达式。这 �n 个选项的标号分别是 �,�,�,�⋯A,B,C,D⋯

输入中的表达式的长度都不超过 5050 个字符，而且保证选项中总有表达式和题干中的表达式是等价的。

输出格式

一行，包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

输入输出样例

输入 #1复制

( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a

输出 #1复制

AC

说明/提示

• 对于 30%30% 的数据，表达式中只可能出现两种运算符 ++ 和 --；
• 对于其它的数据，四种运算符 ++，--，**，^^ 在表达式中都可能出现。
• 对于 100%100% 的数据，表达式中都可能出现小括号 (( 和 ))，2≤�≤262≤n≤26。

【题目来源】

NOIP 2005 提高组第四题

余观此题，未生特殊代值之意，徒有多项式运算之情。所以然者何？变量单一，形式有限，假一数组，以次数顺列系数，则神形兼备，功能俱全。遂写结构，用重载。又用栈，以计算。

说明白点，就是直接拿个结构体，用多项式每项前的系数存成一个数组，来表示多项式，然后通过重载运算符来支持多项式的各种运算。但这里有个问题，就是a的最高次数可能远远超过10。事实上，有一个测试点的数据就有

(a -6)^10^10

所以多项式数组的大小不能只开到11。但这样的话，这个数组岂不是要开的非常大？然而既然可以用代特殊值的方法来做，我以为，算一下目标和结果的“较低”次数也可以管中窥豹略见一斑。即：如果两个多项式在�N次以内的系数都相等，并且�N足够大的时候，也可以判定两个多项式是相等的。这里�N取到100就可以过这题了，也不会出现TLE的问题。这个题解之前没有考虑溢出的问题，最近经过评论区提醒，系数数组需要开long long。

但严格来说，将系数对大数(如1e9+7)取模是更严谨的做法。这种做法另一个问题就是代码量比较大，可能需要比较长的编码调试时间。这个思路主要优势是比较直观，也容易想到。另外写的这个struct非常实用。print()稍微完善一下，或者不完善，因为也能看懂，这已经可以用来做数学作业啦！

(原题解发布于2018-09-24，2021-02-25更新）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<vector>
#include<stack>
#include<string>
#define N 100
using namespace std; struct poly{long long p[N+2];void clear(){memset(p, 0, sizeof(p));}poly operator= (const poly &b){this->clear();for (int i=0; i<=N; i++) p[i]=b.p[i];return *this;}poly operator= (const int b){this->clear();p[0]=b;return *this;}poly operator+ (const poly &b) const{poly c;for (int i=0; i<=N; i++){c.p[i]=p[i]+b.p[i];}return c;}poly operator- (const poly &b) const{poly c;for (int i=0; i<=N; i++){c.p[i]=p[i]-b.p[i];}return c;}poly operator* (const poly &b) const {poly c;c.clear();for (int i=0; i<=N; i++){for (int j=0; j<=N; j++){if (i+j>N) continue;int k=i+j;c.p[k]+=p[i]*b.p[j];}}return c;}poly pow(const poly &b) const {//b must be an integer.int t=b.p[0];poly ans; ans=1;poly pas; pas=(*this);while (t){if (t&1) {ans=ans*pas;}pas=pas*pas;t>>=1;}return ans;}void print(){for (int i=N; i>=0; i--){if (p[i]==0) continue;if (i!=N) cout<<'+';cout<<p[i]<<"a^"<<i;}cout<<endl;}bool operator== (const poly&b) const {for (int i=0; i<=N; i++){if (p[i]!=b.p[i]) return false;}return true;}};stack<poly> s1;
stack<char> s2;inline int f(char c){if (c=='^') return 3;if (c=='*' ) return 2;if (c=='+' || c=='-') return 1;else return 0;
}inline void js(){poly a, b; char c;poly ans;b=s1.top(); s1.pop();a=s1.top(); s1.pop();c=s2.top(); s2.pop();if (c=='+') ans=a+b;if (c=='-') ans=a-b;if (c=='*') ans=a*b;if (c=='^') ans=a.pow(b);s1.push(ans);
}const char L[18]="0123456789+-*^a()";inline bool legal(char c){for (int i=0; i<17; i++){if (c==L[i]) return true; }return false;
}inline poly read(){string s;getline(cin, s);int len=s.size();int judge=0; bool ok=1;if (s.empty()) ok=0;for (int i=0; i<len; i++){if (s[i]=='(') judge++;if (s[i]==')') judge--;if (judge<0) ok=0;}if (judge>0) ok=0;if (!ok) {poly wrong; wrong.clear(); wrong.p[N+1]=1; return wrong;}//gets(s);bool flag=0; int temp=0; poly pt;poly a; a.clear(); a.p[1]=1;for (int i=0; i<len; i++){char &n=s[i];if (!legal(n)) continue;if (n=='a') {s1.push(a); continue;}if (n>='0' && n<='9') {temp=(temp<<1)+(temp<<3)+n-'0'; flag=1; continue;}if (flag) {pt=temp; s1.push(pt); temp=0; flag=0;}if (n=='(') {s2.push(n); continue;}if (n==')') {while (s2.top()!='(') js();s2.pop();continue;}while (!s2.empty() && f(s2.top())>=f(n)) js();s2.push(n);}if (flag) {pt=temp; s1.push(pt);}while (!s2.empty()) js();poly res=s1.top();s1.pop();return res;//s1.top().print();
}int main(){poly aim; aim=read();//aim.print();int n; scanf("%d\n", &n);  for (int i=0; i<n; i++){poly now=read();//now.print();if (now==aim) {char c='A'+i; cout<<c;}}cout<<endl;	return 0;
}