本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-18 10:33:04

看了一圈题解区只有我用了暴力展开 /jy

实际上并不难，还有点水，也不难调。

相信各位应当都会中缀表达式的计算：我们维护一个符号栈和一个数据栈，然后分类讨论根据优先级计算即可。这一点不管是别的题目还是题解区已经讲的很好了，OI Wiki 上的讲解也不错。

这篇题解的重点是把普通整数上的操作扩展到多项式。

由于只有一个字母，我们可以维护系数向量 $v$，其中 $v_k$ 代表 $a^k$ 的系数，常数就是 $a^0$ 的系数。于是，我们就可以用 $O(k)$ 时间做到加减操作。

然后考虑乘和乘方。先考虑朴素的 $O(n^2)$ 乘法。（通过手工模拟可得），代码为：

for (int i = 0; i < K; i++)
  	for (int j = 0; i + j < K; j++) 
      	r.k[i + j] += k[i] * x.k[j];

如果要求更高的速度，可以用 FFT 优化。但是本题数据范围比较小，所以不用。

乘方可以用经典的快速幂，复杂度是 $O(k^2\log n)$ 的，或者是 $O(k \log^2 n)$（FFT 优化）。

接下来就是代码时间了，其实思路是非常好想的。

但是有几点注意：

• 数据换行符含有 \r，不能简单地用 getline

• 最后一个点卡爆 long long，所以需要对这个多项式取模（所以不妨用 NTT）

• 括号可能不匹配 遇到这种情况，应该直接丢掉多余的括号

接下来放看起来还是很不错的代码：

#include <iostream>
#include <stack>
#include <cstring>
#define siz(x) static_cast<int> ((x).size ())
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 30, K = 500, P = 998244353;

class poly {
public:
	int k[K];
	
	poly () { memset (k, 0, sizeof k); }
	poly (const poly &x) { memcpy (k, x.k, sizeof k); }
	poly &operator = (const poly &x) { memcpy (k, x.k, sizeof k); return *this; }
	poly (int x, bool flag = false) { memset (k, 0, sizeof k), k[flag] = x; }
	poly operator + (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) r.k[i] = (k[i] + x.k[i]) % P;
		return r;
	}
	
	poly operator - (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) r.k[i] = (k[i] + P - x.k[i]) % P;
		return r;
	}
	
	poly operator * (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) for (int j = 0; i + j < K; j++) (r.k[i + j] += k[i] * x.k[j] % P) %= P;
		return r;
	}
	
	poly operator ^ (int x) {
		poly r = *this, p = *this;
		--x;
		while (x) {
			if (x & 1) r = r * p;
			x >>= 1, p = p * p;
		}
		return r;
	}
	
	bool operator == (const poly &x) {
		for (int i = 0; i < K; i++) if (k[i] != x.k[i]) return false;
		return true;
	}
	
	friend ostream &operator << (ostream &out, const poly &x) {
		for (int i = K - 1; i >= 2; i--) if (x.k[i]) {
			if (x.k[i] == 1) out << "a^" << i << " + ";
			else if (x.k[i] == -1) out << "-a^" << i << " + ";
			else out << x.k[i] << "a^" << i << " + ";
		}
		if (x.k[1] == 1) out << "a + ";
		else if (x.k[1] == -1) out << "-a + ";
		else if (x.k[1]) out << x.k[1] << "a + ";
		out << x.k[0];
		return out;
	}
};


stack<char> op;
stack<poly> q;

void ins (char c)
{
	poly y, x;
	
	if (c == '(') return;
	if (q.empty ()) cout << "fuck off", exit (0);
	y = q.top (), q.pop ();
	if (q.empty ()) cout << "fuck off", exit (0);
	x = q.top (), q.pop ();
	switch (c) {
	case '+': q.push (x + y); break;
	case '-': q.push (x - y); break;
	case '*': q.push (x * y); break;
	case '^': q.push (x ^ y.k[0]); break;
	default: break;
	}
}

int prio (char c)
{
	switch (c) {
	case '(': return 0;
	case '+': case '-': return 1;
	case '*': return 2;
	case '^': return 3;
	default: return -1;
	}
}

bool space (char c) { return c == ' ' || c == '\n' || c == '\r'; }

poly expand (void)
{
	int level = 0;
	char c;

	while (!q.empty ()) q.pop ();
	while (space (c = getchar ()));
	do {
		if (isdigit (c)) {
			int x = 0;
			do x = (x * 10 % P + c - '0') % P; while (isdigit (c = getchar ()));
			while (space (c) && c != '\n') c = getchar ();
			q.push (poly (x));
			if (c == '\n') break;
			else continue;
		}
		
		switch (c) {
		case 'a': q.push (poly (1, true)); break;
		case '(': op.push ('('), level++; break;
		case ')':
			if (--level < 0) break;
			while (!op.empty () && op.top () != '(') ins (op.top ()), op.pop ();
			op.pop (); break;
		default:
			while (!op.empty () && prio (op.top ()) >= prio (c)) ins (op.top ()), op.pop ();
			op.push (c); break;
		}
		while (space (c = getchar ()) && c != '\n');
	} while (c != '\n');
	
	while (!op.empty ()) ins (op.top ()), op.pop ();
	return q.top ();
}

int read (void)
{
	int res = 0;
	char c;
	while (!isdigit (c = getchar ()));
	do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
	return res;
}

signed main (void)
{
	int n;
	poly res;
	
	res = expand ();
	n = read ();
	
	for (int i = 1; i <= n; i++) if (expand () == res) putchar ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"[i - 1]);
	putchar ('\n');
	return 0;
}