记录编号	305693	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]等价表达式	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2016-09-10 23:35:22	内存使用	0.31 MiB

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <stdarg.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <string>
#include <iostream>
using namespace std;
#define MOD 998244353
typedef long long LL;
LL aval;
int getwei(char op)
{
    switch(op)
    {
        case '^':
            return 1;
        case '*':
            return 2;
        case '+':
        case '-':
            return 3;
        default:
            return 0;
    }
}

LL ipow(LL base, LL exp)
{
    base %= MOD;
    LL ans = 1;
    while(exp)
    {
        if(exp & 1)
            ans = (ans*base)%MOD;
        exp >>= 1;
        base = base*base%MOD;
    }
    return ans;
}
LL calc(const char *expr, int len)
{
    int bk = 0;
    int pos = 0, w = 0;
    for(int i = 0; i < len; i++)
    {
        if(expr[i] == ' ')continue;
        if(expr[i] == '(')bk++;
        else if(expr[i] == ')')bk--;
        if(bk)continue;
        int nw = getwei(expr[i]);
        if(nw >= w)
        {
            w = nw;
            pos = i;
        }
    }
    if(w > 0)
    {
        switch(expr[pos])
        {
            case '+':
                return (calc(expr, pos)+calc(expr+pos+1, len-pos-1))%MOD;
            case '-':
                return (calc(expr, pos)-calc(expr+pos+1, len-pos-1))%MOD;
            case '*':
                return (calc(expr, pos)*calc(expr+pos+1, len-pos-1))%MOD;
            case '^':
                return ipow(calc(expr, pos), calc(expr+pos+1, len-pos-1));
        }
    }
    for(int i = 0; i < len; i++)
    {
        if(expr[i] == '(')
            return calc(expr+1+i, len-2-i);
        else if(expr[i] == 'a')
            return aval;
    }
    return atoi(expr);
}
#define MAXN 233
int main()
{
    freopen("equal.in", "r", stdin);
    freopen("equal.out", "w", stdout);
    string me;
    string eat;
    getline(cin, me);
    int n;
    cin >> n;
    getline(cin, eat); 
    for(int i = 0; i < n; i++)
    {
        string tmp;
        getline(cin, tmp);
        bool flag = true;
        for(int j = 0; j < 100; j++)  //测试100次
        {
            aval = (rand()%233)+10;
            if((calc(me.c_str(), me.length())+MOD)%MOD != (calc(tmp.c_str(), tmp.length())+MOD)%MOD)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            cout << (char)(i+'A');
    }
    return 0;
}