核心思想是将无法处理的运算参量单独设为一个未知量,也就是变成维护二元组,多个未知量就是多元组,然后设置它们的合并规则进行计算。
一般而言,最终的未知量都会消去。
例如 NOI2025 集合 中,我们需要涉及到处理含 \(0\) 算式的乘除法,可以将数字表达为 \(x·0^y\) 的形式,用二元组 \((x,y)\) 来维护。
不过显而易见的只支持乘除法以及 \(y=0\) 的加减法,但这足以。
另一个例子是斐波那契数列,\(f_n=\frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5}\)
常见的算法是用矩阵乘法,但更快的做法是:
- 若存在 \(x^2\equiv 5 (\bmod p)\) 则可以直接带入 \(x\) 进行计算。
- 设变量 \(t=\sqrt 5\),将数字 \(x+y\sqrt 5\) 记作 \((x,y)\),重定义运算:
- \((a,b)+(c,d)=(a+c,b+d)\)
- \((a,b)\times (c,d)=(ac+t^2bd,ad+bc)\)
由于是 \(\sqrt 5\) 的形式,\(t^2=5\),因此事实上是维护的一个关于 \(t\) 的一次多项式的运算。
其他类似的也可以这样做,或者说可以直接将其当做一个正常的数字来运算,例如 P5320 之中的 \(\sqrt 3\)。
扩展一下,若式子中同时含有 \(\sqrt 3,\sqrt 5\),可以设计变量 \(a=\sqrt 3,b=\sqrt 5,c=\sqrt 15\) 维护四元组。
若含有 \(3^{\frac{1}{3}}\) 之类的数字,可以设计 \(a=3^{\frac{1}{3}},b=3^{\frac{2}{3}}\) 来进行运算。
事实上都是含变量的多项式运算,只不过定义了新的四则运算规则。