设a为一个质数，模数为另一个质数，然后暴力算多项式的答案，如果答案相等就认为两个多项式相等。
这种hash有出错概率的题为什么还是要用hash呢？因为出错的概率实在太小了，a和模数的值取得好出题人根本没法卡。
然后贡献了2次WA，第一次因为判断数字时没判断边界，第二次因为乘法运算时爆int了！！！
hash大法好～
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 10003;
const int a = 10007;
const int p = 100007;char s[N], c[N], stf[N];
int num, now, stnum[N], topnum, sty[N], topfh;
int get(char c) {if (c == '+' || c == '-') return 1; if (c == '*') return 2; if (c == '^') return 3;}
bool fh(char c) {return c == '+' || c == '-' || c == '*' || c == '^' || c == '(' || c == ')';}
int ipow(int a, int b) {
ll s = 1;
for(int i = 1; i <= b; ++i)
s = s * a % p;
return (int) s;
}
int cal(char fh, int a, int b) {
switch (fh) {
case '+':
return (a + b) % p;
break;
case '-':
return (a - b + p) % p;
break;
case '*':
return (int) (1ll * a * b % p);
break;
case '^':
return ipow(a, b);
break;
}
}
int _() {
int len = strlen(s), tmp = 0, j = 100, k;
c[0] = ' ';
for(int i = 0; i < len; ++i)
if (s[i] != ' ') c[++tmp] = s[i];
c[tmp + 1] = ' ';
len = tmp; tmp = 1; topnum = topfh = 0;
while (tmp <= len) {
if (fh(c[tmp])) {
if (c[tmp] == '(') j += 10;
else if (c[tmp] == ')') j -= 10;
else {
k = get(c[tmp]);
while (topfh && sty[topfh] >= k + j) {
stnum[topnum - 1] = cal(stf[topfh], stnum[topnum - 1], stnum[topnum]);
--topnum; --topfh;
}
stf[++topfh] = c[tmp]; sty[topfh] = k + j;
}
++tmp;
} else {
if (c[tmp] == 'a') stnum[++topnum] = a, ++tmp;
else {
k = 0;
for(;c[tmp] >= '0' && c[tmp] <= '9' && tmp <= len; ++tmp)
k = k * 10 + c[tmp] - '0';
stnum[++topnum] = k;
}
}
}
while (topfh) {
stnum[topnum - 1] = cal(stf[topfh], stnum[topnum - 1], stnum[topnum]);
--topnum; --topfh;
}
return stnum[1];
}
int main() {
gets(s);
num = _();
int m;
scanf("%d\n", &m);
for(int i = 0; i < m; ++i) {
gets(s);
now = _();
if (now == num) putchar('A' + i);
}
puts("");
return 0;
}
神奇的hash啊，你的低错误率是多么玄学，你的可靠性那么扑朔迷离～
