万能欧几里得

BJpers2 · 2020-08-06 15:05:38 · 个人记录

类欧几里得在OI当中相当冷门，因为其过于复杂的推理难度和繁琐的实现细节劝退效果实在太强。

但名为「万能欧几里得」的算法则可以帮我们绕过这些繁琐的推理步骤，简洁明了地触及问题的本质。

事实上，如果掌握了本算法，那么做一般的类欧几里得题时，你的草稿纸上甚至不必出现任何求和符号。

一、问题转化

类欧几里得题大概有如下的形式：

设y=\left \lfloor \frac {px+r}q\right\rfloor

求

\sum_{x=1}^n y,\sum_{x=1}^n xy,\sum_{x=1}^n y^2,\sum_{x=1}^n a^xy,\sum_{x=1}^n a^xb^y,\dots

这些问题又可以统一换作如下表述：

作出函数y= \frac {px+r}q的图像，之后从左往右考虑该线与网格线的交点，维护一个列向量，遇横线则乘矩阵U，遇竖线则乘矩阵R（同时相遇则优先乘U），求刚走过n条竖线后的最终向量。

可以发现上述求和问题，均可以通过合理选取维护的向量\boldsymbol{v}以及矩阵U,R来转化为矩阵乘积问题。

例如求\sum y，则可以取(\boldsymbol{v},U,R)为：

可以看出这样做矩阵乘法实时地正确维护了左边的三个量。

再如求\sum a^x y，我们也可以设计(\boldsymbol{v},U,R)如下：

又如求\sum xa^xy^2b^y，我们照样可以大力写出：

因此，我们只需设计解决矩乘问题的算法，类欧问题便能得到解决。

二、解决思路

我们形式化地将这个问题表述如下：

给定一个含有n个R的U,R矩阵序列，序列末尾是R。第x个R前恰有y=\left \lfloor \frac {px+r}q\right\rfloor个U。

求这些矩阵的乘积。

我们把上述问题的答案记为\text{sol}(p,q,r,n,U,R)。

为了使整个问题的形式更为严整，我们规定r<q。

接下来可以用如下方式缩小问题的规模：

1. 合并

注意到，当p\ge q时，每个R之前都至少有\left \lfloor \frac p q\right\rfloor个连续的U，那么我们把这些U和R合并到一起形成新的R，这样每个R之前还剩的U个数为：

于是我们得到

这一步操作的意义在于，p的规模能得以大幅减小。从几何的角度来讲，它相当于把直线按y轴缩小到斜率<1，缩放中心为直线yq=r。

2. 翻转

考察第y个U之前的R个数，它是关于x的不等式

的最大整数解。

我们可以在整数上的解集不变的情况下对不等式进行改写：

此时U的个数为m=\left\lfloor\frac{pn+r}q\right\rfloor。

但是我们并不能就这样开心地把问题转化为\text{sol}(q,p,-r-1,m,R,U)。我们还需解决以下两个问题：

• 新的r应当在[0,p)范围内。
• 原序列以R结尾，翻转后以U结尾，这导致转化后不满足序列末尾是R。

对于第一个问题，我们把翻转前第一个U以及其前面的所有R单独拿出来算。

这样一来，现在的第y个U是原先第y+1个U，其前的R的个数变为：

这样新的r就恰好在[0,p)范围内了。

对于第二个问题，我们把翻转前最后一段R单独拿出来算即可，最后总共有n-\left\lfloor\frac{qm-r-1}p\right\rfloor个R，下取整中计算了最后一个U前R的数目。

于是我们又得到：

当然，m等于0时并不符合递归条件，但这将意味着整个序列中不存在U，于是此时有：

这一步操作事实上将直线关于y=x进行了对称，随后左移1个单位，为了处理直线过格点时的特例，我们在将其下移\frac 1 p个单位。

3. 合并

注意到操作1,2必然是交替进行的，那么我们可以把它们合并起来，即：

注意到，如果p=0，由m=\left\lfloor\frac{pn+r}q\right\rfloor,r<q可知m必为0，那么此时递归结束。

而p,q的变化与求\gcd(p,q)时它们的变化完全一致，因此递归的层数是O(\log p)级别。

三、实现细节

1. 经过上一节的讨论，我们已经将问题足够地标准化了，因此并不需要通过大量特判处理p,q,r,n的各种边界情况。

3. 一般题目初始并不会保证p,r\in[0,q)，我们只需求R^{\left\lfloor\frac r q\right\rfloor}\text{sol}(p\bmod q,q,r \bmod q,n,U,U^{\left\lfloor\frac p q\right\rfloor}R)。

4. 可以通过适当封装降低代码复杂度。

算法的大致框架如下：

ele operator ^ (ele x,ll y){ele z;for(;y;y>>=1,x=x*x)if(y&1) z=z*x;return z;}
ele sol(ll p,ll q,ll r,ll n,ele U,ele R){
    ll m=(p*n+r)/q-1;
    return ~m?r=q-r-1,(R^r/p)*U*sol(q%p,p,r%p,m,R,(R^q/p)*U)*(R^n-(q*m+r)/p):R^n;
}
int main(){
    ans=(U^r/q)*sol(p%q,q,r%q,n,U,(U^p/q)*R);
}

只要合理的设计元素，并规定乘法。上述代码就能准确无误地运行任何目前已知的类欧几里得问题。

四、缺陷

尽管万能欧几里得具有代码好写，拓展性强的优势，它仍然无法解决某些特殊的问题，例如

事实上，如果求和号内的部分关于x,y中任意一个的差分影响不是线性的，我们就难以设计出合理的U,R矩阵并套用万能欧几里得解决。

所以目前看起来可以解决的问题是：

其中f,g是分别关于x,y的多项式。