EX 中缀表达式题解

· · 题解

感谢洛谷把 GDKOI 放上来了！借这道题来庆祝我普及金奖！

【GDKOI2024 普及组】EX 中缀表达式的题解

在这里提出我的建议：

题目大意

这是一道数学、模拟题，要求计算表达式的值并且按照它规定的优先级和结合的左右顺序进行处理并模 10^9+7 输出，还要判断表达式是否合法，符号只有 +、* 和 ^。

前置芝士

考场上的情况（不想看的可以跳过）

先说一下我比赛时的情况：那时我非常智慧，看到这道题一眼模拟直接无脑开始狂打。像这种表达式求值的题很明显的做法是将中缀表达式转成后缀表达式，然后进行求值。因为打熟悉了中缀表达式转成后缀表达式，所以很快打完，并且 Error 判断的也比较好，最后一直过不了样例，甚至叫来老师问是不是样例出错了（因为样例有次方运算，我又把次方给进行了模运算，导致直接暴力算都是错的），最后也是不明不白地离开了考场。出来和同学讨论以后才发现次方运算的次方不可以直接模。结果还怀疑人家题出错了【捂脸】。最后居然还能拿没有次方运算的 16 分。加上 Error 的 12 分（有两个没有判断到）。

正解

其实就是暴力，只不过细节有亿点点多。

难点

判断不合法的 Error 情况：

首先判断不合法的中缀表达式有以下几种：

将中缀表达式转成后缀表达式

个人认为这是比较简单的一步，只要你学过中缀表达式转成后缀表达式。在这里还是讲一下步骤吧：

我们用一个字符栈来维护这个过程。

这时我们就得到了一个后缀表达式。

将次方取模时的处理（乘方运算在取模意义下的取值）

对于次方来说确实不好办的，不可以直接取模，所以这应该是最难的一个点了，我们需要用到一个数学推论：扩展欧拉定理。

这里给出式子：

a^b\equiv \begin{cases} a^{\left(b\ \bmod \ \varphi(p) \right)},&\gcd(a, p)=1 \\ a^b,& \gcd(a,p)\ne1,b<\varphi (p) \\ a^{\left(b\ \bmod \ \varphi(p) + \varphi(p) \right)},&\gcd(a, p)\ne1,b\ge \varphi (p) \end{cases}

我们发现不能仅仅靠后缀表达式，我们需要建立一颗后缀表达式树，因为我们需要先算出 a，然后根据 a 是否与 p 互质分类（p 指的是当前的模数），然后再递归 b 改变它的模数为 \varphi(p)。对于每个数字或字符直接动态开点记录左右儿子即可。

接下来的操作对于加法和乘法是比较简单的，我们直接将它们取模返回值即可。

当我们遇到次方运算时，我们需要计算 a^b，a 是很容易得到的，直接递归左边的子树（a 的子树下的值是可以直接 \mod p 的），得到 a 的值以后我们看 \gcd(a,p) 是否为 1（是否互质）。

如果互质也就是第一种情况就非常简单，求得 \varphi (p) 后把它当成 b 的子树的模数下传得到之后返回快速幂计算即可。

发现不互质的情况还是很麻烦，需要判断 b 与 \varphi (p) 的大小。但 b 下到子树下可能还会多次改变模数从而改变 b 原来有的值，所以我们为了判断 b 的大小再预处理一遍整颗后缀表达式树，算出 \varphi (p) 后每次在 b 运算时及时判断它什么时候超过了 \varphi (p)，超过了我们记录一个数组 q 的值为 -1，没超过就直接记录 b 的值，这样就可以对 b 的大小分类，如果是 -1 或者当前的 q 值比当前的 \varphi (p) 要大表示应该是上述第三种情况，否则已经得到了 b 的值（在 q 里面）直接运算即可。

这样就能发现获得了 84pts。

最后发现输入的数字还有可能是一个很多位数的数字，必须用高精度来存储，只用在刚开始的数字中计算即可（因为上传的时候会模数）。建议高精度用结构体存储,并只在表达式树下层叶子节点数字计算高精度时使用，上层取模后可以直接存储。

代码有点小多，要坚持下去才能打败这种大模拟题！

Code

详见云剪贴板