題目描述

明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個很麻煩的選擇題。這個題目的題干中首先給出了一個代數(shù)表達(dá)式，然后列出了若干選項，每個選項也是一個代數(shù)表達(dá)式，題目的要求是判斷選項中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價的。

這個題目手算很麻煩，因為明明對計算機編程很感興趣，所以他想是不是可以用計算機來解決這個問題。假設(shè)你是明明，能完成這個任務(wù)嗎？

這個選擇題中的每個表達(dá)式都滿足下面的性質(zhì)：

1. 表達(dá)式只可能包含一個變量?�a。
2. 表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于?1000010000。
3. 表達(dá)式中可以包括四種運算?++（加），--（減），**（乘），^^（乘冪），以及小括號?((，))。小括號的優(yōu)先級最高，其次是?^^，然后是?**，最后是?++?和?--。++?和?--?的優(yōu)先級是相同的。相同優(yōu)先級的運算從左到右進(jìn)行。（注意：運算符?++，--，**，^^?以及小括號((，))?都是英文字符）
4. 冪指數(shù)只可能是?11?到?1010?之間的正整數(shù)（包括?11?和?1010）。
5. 表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。

下面是一些合理的表達(dá)式的例子：

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

輸入格式

第一行給出的是題干中的表達(dá)式。

第二行是一個整數(shù)?�n，表示選項的個數(shù)。后面�n行，每行包括一個選項中的表達(dá)式。這?�n?個選項的標(biāo)號分別是?�,�,�,�?A,B,C,D?

輸入中的表達(dá)式的長度都不超過?5050?個字符，而且保證選項中總有表達(dá)式和題干中的表達(dá)式是等價的。

輸出格式

一行，包括一系列選項的標(biāo)號，表示哪些選項是和題干中的表達(dá)式等價的。選項的標(biāo)號按照字母順序排列，而且之間沒有空格。

輸入輸出樣例

輸入 #1復(fù)制

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

輸出 #1復(fù)制

AC

說明/提示

• 對于?30%30%?的數(shù)據(jù)，表達(dá)式中只可能出現(xiàn)兩種運算符?++?和?--；
• 對于其它的數(shù)據(jù)，四種運算符?++，--，**，^^?在表達(dá)式中都可能出現(xiàn)。
• 對于?100%100%?的數(shù)據(jù)，表達(dá)式中都可能出現(xiàn)小括號?((?和?))，2≤�≤262≤n≤26。

【題目來源】

NOIP 2005 提高組第四題

余觀此題，未生特殊代值之意，徒有多項式運算之情。所以然者何？變量單一，形式有限，假一數(shù)組，以次數(shù)順列系數(shù)，則神形兼?zhèn)?#xff0c;功能俱全。遂寫結(jié)構(gòu)，用重載。又用棧，以計算。

說明白點，就是直接拿個結(jié)構(gòu)體，用多項式每項前的系數(shù)存成一個數(shù)組，來表示多項式，然后通過重載運算符來支持多項式的各種運算。但這里有個問題，就是a的最高次數(shù)可能遠(yuǎn)遠(yuǎn)超過10。事實上，有一個測試點的數(shù)據(jù)就有

(a -6)^10^10

所以多項式數(shù)組的大小不能只開到11。但這樣的話，這個數(shù)組豈不是要開的非常大？然而既然可以用代特殊值的方法來做，我以為，算一下目標(biāo)和結(jié)果的“較低”次數(shù)也可以管中窺豹略見一斑。即：如果兩個多項式在�N次以內(nèi)的系數(shù)都相等，并且�N足夠大的時候，也可以判定兩個多項式是相等的。這里�N取到100就可以過這題了，也不會出現(xiàn)TLE的問題。這個題解之前沒有考慮溢出的問題，最近經(jīng)過評論區(qū)提醒，系數(shù)數(shù)組需要開long long。

但嚴(yán)格來說，將系數(shù)對大數(shù)(如1e9+7)取模是更嚴(yán)謹(jǐn)?shù)淖龇ā＿@種做法另一個問題就是代碼量比較大，可能需要比較長的編碼調(diào)試時間。這個思路主要優(yōu)勢是比較直觀，也容易想到。另外寫的這個struct非常實用。print()稍微完善一下，或者不完善，因為也能看懂，這已經(jīng)可以用來做數(shù)學(xué)作業(yè)啦！

(原題解發(fā)布于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;
}