问题引入：求 $\sum_{i=1}^n\lfloor\frac{a\times i+b}{c}\rfloor$。期望复杂度 $O(T\log n)$。
考虑引入函数 $y=\frac{ax+b}{c}$，$x\in(0,n]$，则从 $x=0$ 出发，维护两个变量 $A,B$ 初始为 $0$，执行以下操作：
- 遇到 $y=h$ 就让 $A\gets A+1$；
- 遇到 $x=k$ 就让 $B\gets B+A$。
优先执行第一条，最终的 $B$ 就是答案。不难发现 $b$ 可以直接对 $c$ 取模，因为在这个转化后的问题中只关心越过两类网格线的次数。
不妨写下一个字符串 $S$，过程中每遇到一次 $y=h$ 就在末尾写下一个 U，每遇到一次 $x=k$ 就在末尾写下一个 R，最终的答案只和这个字符串有关。
考虑把这两种规则看作某种线性变换（容易构造矩阵表示/合并），分别为 $f_U,f_R$，即向上越过网格线和向右越过网格线的影响。即答案为初始两个变量，依次经过 $S$ 中的每一个变换后最终得到的值。由于结合律可以优先合并变换。
更形式化一点，记 $g(a,b,c,n,f_U,f_R)$ 为这个过程后合并得到的变换，进行一些讨论：
- 若 $a\ge c$，则每个
R前至少有 $\lfloor\frac{a}{c}\rfloor$ 个U，把它们合并起来，则答案为 $g(a\bmod c,b,c,n,f_U,f_U^{\lfloor\frac{a}{c}\rfloor}\cdot f_R)$； 若 $a<c$，尝试类似辗转相除法地交换 $a,c$，那么要交换
U,R的地位：第 $p$ 个
R前共有 $\lfloor\frac{ap+b}{c}\rfloor$ 个U，假设第 $q$ 个U在第 $p$ 个R之后：- $q>\lfloor\frac{ap+b}{c}\rfloor\ge \frac{ap+b}{c}$，移项得 $p<\frac{cq-b}{a}$，由于 $a,b,c,q,p\in\mathbb{Z}^+$，有 $p\leq \lfloor\frac{cq-b-1}{a}\rfloor$。
- 那么第 $q$ 个
U前共有 $\lfloor\frac{cq-b-1}{a}\rfloor$ 个R，注意其包括与其同时加入的R。 - 转化为了另一个形式类似的问题，即 $y=\frac{cx-b-1}{a}$，$y\in(0,n]$，求总变换。不妨设 $m=\lfloor\frac{an+b}{c}\rfloor$，则 $x\in(0,m]$。
现在面临和原问题不同的部分是：
- $b'=-b-1$，不满足 $b'\in[0,c')$；
- 在 $x>m$ 时虽然没有新的
R，但可能存在部分U未被写入。
- 对于第一个问题，由于 $c-b-1\ge 0$，可以通过特殊计算 $x\leq 1$ 的部分再递归剩下部分来解决；对于第二个问题，可以特殊计算 $x>m$ 部分
U的个数来解决。 - 特殊地，递归的边界是 $m=0$ 时返回 $f_R^n$。否则递归计算 $f_R^{\lfloor\frac{c-b-1}{a}\rfloor}\cdot f_U\cdot g(c,c-b-1,a,m-1,f_R,f_U)\cdot f_R^{n-\lfloor\frac{cm-b-1}{a}\rfloor}$。
设计算一次 $f\cdot f\to f$ 的复杂度是 $O(t)$，则计算 $f^k$ 的复杂度是 $O(t\log k)$，每轮递归的 $k=O(\frac{a}{c})$，则复杂度为 $O(t\log a-t\log c)$，总复杂度 $T(a,c)=T(c,a\bmod c)+O(t\log a-t\log c)=O(t\log \max\{a,c\})$。
对于这个例题（【模板】类欧几里得算法 的第一部分），需要维护三元组 $(cntU,cntR,ans)$ 表示经过的 U,R 的个数以及当前答案，初始 $f_U=(1,0,0),f_R=(0,1,0)$。那么合并三元组 $(a,b,c)\cdot (d,e,f)=(a+d,b+e,c+f+ae)$，注意在题目限制下需要额外加上 $i=0$ 的答案。本质是后半部分贡献 $y\to (y+a)$。
第二部分需要求 $\sum_{i=0}^n{\lfloor\frac{ai+b}{c}\rfloor}^2$，合并依赖第一部分的和，即后半部分的贡献 $y^2\to (y+a)^2$。
第三部分需要求 $\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor$，合并依赖第一部分的答案以及 $x$ 的和，即后半部分的贡献 $xy\to (x+a)(y+b)$。
实际代码实现中只需要修改合并部分，递归部分都是完全一致的。
node g(int a,int b,int c,int n,node U,node R){
if(!n)return node();if(b>=c)b%=c;
if(a>=c)return g(a%c,b,c,n,U,U*(a/c)+R);
int m=(a*n+b)/c;if(!m)return R*n;
return R*((c-b-1)/a)+U+g(c,c-b-1,a,m-1,R,U)+R*(n-(c*m-b-1)/a);
}在本题中三个部分一共需要维护 6 个变量分别表示 $y,x,\sum x,\sum y,\sum y^2,\sum xy$，注意 $f_U,f_R$ 的初始值有不同，因为 R 比 U 多一个结算，所以初始 $f_U$ 中仅有 $y=1$，$f_R$ 中有 $x=\sum x=1$。
4 条评论
哇，moyujiang
哇，moyujiang
哇，moyujiang
哇，moyujiang