之前有个题是类欧求 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