之前有个题是类欧求 floor sum，感觉素质不是很高。
后来又有个题是万欧，这下这下了。
考虑这样一个事情：我们有一个 向量 \(v\)，考虑有一条线段 \(y=\frac{ax+b}{c}\)，其中 \(a,b,c\) 均为自然数且 \(c\gt 0\)，定义域为 \((0,n]\)。
注意是右闭左开的。
这条线段随着 \(x\) 的增加，当碰到 \(x=k\) 的整线的时候，我们就对 \(v\) 做一次线性变换：\(v:=vR\)；当碰到 \(y=k\) 的整线的时候，就对 \(v\) 做一次 \(v:=vU\) 的线性变换；如果是整点，则先做 \(U\) 后做 \(R\)。然后我们需要求出最后的 \(v\)。
显然我们最后只需要求出那个线性变换矩阵，设为 \(T\)，然后 \(vT\) 就是答案。
为什么会发明出来这么奇怪的东西？其实有一个实际背景就容易理解了：我们可能维护的是一个变量 \(a\)，这个 \(a\) 有一个变化规律，而我们要求 \(a\) 在某些时刻的和。
那么可以尝试构造一条线段：使得它碰到 \(y=k\) 的时候恰好就是 \(a\) 这个变量更新的时刻，然后线性变换 \(U\) 就等价于对变量 \(a\) 更新；当碰到 \(x=k\) 的时候恰好就是把 \(a\) 的当前值累加进答案的时刻，那么线性变换 \(R\) 就等价于 \(sum:=sum+a\) 这样的东西。
由于我们只关心 \((n,a,b,c,U,R)\)，所以把这个六元组记作状态。
可以看出，一个 corner case 是 \(n=0\)，此时 \(T=I\)。
可以看出，我们把整条线段上下平移整数格，不会改变结果，因此可以认为 \(b\in [0,c)\)。
当 \(a\ge c\) 的时候，考察 \((n,a,b,c,U,R)\) 和 \((n,a\bmod c,b,c,U,R)\) 两条线段的结果有什么区别，可以发现每一个 \(R\) 的前面都恰好多了 \(\lfloor \frac{a}{c} \rfloor\) 个 \(U\)，所以可以重定义 \(R:=U^{\lfloor \frac{a}{c}\rfloor}R\) 然后变成 \(a\lt c\) 的情况。
当 \(a\lt c\) 的时候，感觉不是正常人能想到的角度。
注意到上面的线段对应这样一个东西：第 \(i\) 次 \(R\) 变换前共做了 \(\lfloor \frac{ai+b}{c} \rfloor\) 次 \(U\) 变换，记这个值为 \(s_i\)。
则其实就是：做 \(s_1\) 次 \(U\) 变换后做 \(R\) 变换，然后做 \(s_2-s_1\) 次 \(U\) 变换后再做 \(R\) 变换，然后做 \(s_3-s_1\) 次变换后再做 \(R\) 变换...，做 \(s_n-s_{n-1}\) 次变换后再做 \(R\) 变换。
注意到任何一个状态其实都和 \((s_1,s_2,...,s_n)\) 这个序列形成一一对应。
换个视角：第 \(i\) 次 \(U\) 变换前做了几次 \(R\) 变换！？
如果第 \(j\) 次 \(R\) 变换在第 \(i\) 次 \(U\) 变换前，则意味着：
\[aj+b\lt ci \\ j\lt \frac{ci-b}{a} \\ j\le \lfloor \frac{ci-b-1}{a} \rfloor \]如果我们拿一条 \(y=\frac{cx-b-1}{a}\) 的线段，然后交换一下 \(U,R\)，好像两者就等价了。
当然这个只是大体思路，我们会发现有很多锅，最直接的：我们这里 \(-b-1\) 是个负数啊，第二个：新的 \(n\) 取值是多少，第三个：如果最后一个 \(U\) 后面还有 \(R\) 咋办。
首先解决第三个问题，由于 \(m=\lfloor \frac{an+b}{c} \rfloor\) 是原线段最后一次执行 U 变换的位置，所以第 \(m\) 次 \(U\) 变换之后的 \(R\) 都不会被统计进去，我们知道第 \(m\) 次 \(U\) 变换之前的 \(R\) 变换次数是 \(\lfloor \frac{cm-b-1}{a}\rfloor\)，所以最后额外乘上 \(R^{n-\lfloor \frac{cm-b-1}{a} \rfloor}\) 作为修正即可。
然后第二个问题也得到了解决：算到 \(m\) 就够了捏。
第一个问题比较谔谔，注意到 \(c\gt b\)，所以不妨把它变成 \(\frac{cx + (c-b-1)}{a}\)，然后就从 \((0,m]\) 变成了算 \((0,m-1]\)，这样就行了。
此时看似三个问题都解决了，但是我们缺的 \((0,1]\) 这块的线性变换谁给我补啊？
发现这个特判是容易的，在递归的开头乘上 \(R^{\lfloor \frac{c-b-1}{a} \rfloor}\times U\) 即可，也就是把第一个 \(U\) 和它之前的 \(R\) 拿出来特殊算（注意上一个特判是挂在递归结束后面的）。
设一次矩阵乘法的复杂度是 \(O(T)\) 则复杂度看上去是 \(O(T\log^2\max\{n,c\})\) 的，但是通过一些分析可以发现其实是 \(O(T\log\max\{n,c\})\) 的，太困了有空补。
而且发现其实不一定是矩阵乘法（线性变换），只要有结合律就能捣鼓一下了啊。还能解决我们类欧的所有问题，有空补。
题有空补一个。
标签：lfloor,frac,变换,欧几里得,rfloor,线段,线性变换,万能 From： https://www.cnblogs.com/Cry-For-theMoon/p/17489992.html