标题: CF1993F Dyn-scripted Robot (Easy Version&Hard Version) [扩展中国剩余定 [打印本页] 作者: 不到断气不罢休 时间: 2024-10-10 10:18 标题: CF1993F Dyn-scripted Robot (Easy Version&Hard Version) [扩展中国剩余定 传送门:CF [前题提要]:一道扩展中国剩余定理的标题,自从模板题之后就很少遇到这种题,而且是AC的第二道*2800的标题,故写篇题解记载一下 起首考虑 E a s y Easy Easy和 H a r d Hard Hard的区别,不难发现区别是循环的次数.以是猜想一下,显然 E a s y Easy Easy的做法应该是和枚举是第几次循环有关.然后我们会发现显然横坐标和纵坐标是可以分开来考虑.那么为了简朴起见,我们先只考虑横坐标变为0是什么情况. 直接模拟标题,会发现遇到边界翻转操纵序列是一件很难的事变,以是会想到是不是会存在某个规律,考虑手模一下样例或者是本身手造几个样例,诶,会发现每次达到0点的时候事实上是前缀操纵序列和为(2*W)的倍数的时候(此时我们将向右走记为1,向左走记为-1).这个结论非常的重要!!! 固然会有人会怎么注意到这个结论的,只能说运气,或者说一种直觉??
此时我们考虑枚举第几次操纵序列,然后假设当前我们所在的位置是 x x x,那么我们这一次操纵序列经过之后的贡献就是( s u m i sum_i sumi+ x x x)是 2 ∗ W 2*W 2∗W的倍数的个数(我们将前缀和记为 s u m i sum_i sumi),我们将其数学化,也就是问有多少个 ( s u m i + x ) % ( 2 ∗ W ) = 0 (sum_i+x)\%(2*W)=0 (sumi+x)%(2∗W)=0显然的我们可以直接通过预处理出模 2 ∗ W 2*W 2∗W意义下的数的个数,不妨记为 m p [ ] mp[\;] mp[],那么对于每一个 x x x,显然我们的贡献就是 m p [ 2 ∗ W − x ] mp[2*W-x] mp[2∗W−x].注意:考虑到 x < 2 ∗ W , s u m i < 2 ∗ W x<2*W,sum_i<2*W x<2∗W,sumi<2∗W,以是贡献只能是 2 ∗ W 2*W 2∗W 固然上述只是考虑了横坐标的情况,如果我们加入纵坐标的情况,只要开一个二维的累加一下即可.
以是此时我们的 E a s y Easy Easy就解决了,直接模拟即可. 现在考虑 H a r d Hard Hard.显然的,我们得顺着 E a s y Easy Easy得出来的结论去思考.现在我们不能枚举当前是第几次操纵了.其实,这个时候做 C F CF CF题做多了不能枚举的标题,不难会想到是不是可以直接反过来贡献一下.诶,事实上是可以的.对于本题来说,我们反过来想一下,对于 s u m i sum_i sumi,有多少个 x x x能有贡献,那么它们累加起来不就可行了.做 E a s y Easy Easy的时候不难发现经过一次的操纵序列,我们的 x + = s u m x n , y + = s u m y n x+=sumx_n,y+=sumy_n x+=sumxn,y+=sumyn,为了方便起见,我们将 s u m x n sumx_n sumxn记为 d x dx dx, s u m y n sumy_n sumyn记为 d y dy dy.那么我们的 x x x序列是 0 , 0 + d x , 0 + 2 ∗ d x , . . . , 0 + ( k − 1 ) ∗ d x 0,0+dx,0+2*dx,...,0+(k-1)*dx 0,0+dx,0+2∗dx,...,0+(k−1)∗dx,同理, y y y序列是 0 , 0 + d y , 0 + 2 ∗ d y , . . . , 0 + ( k − 1 ) ∗ d y 0,0+dy,0+2*dy,...,0+(k-1)*dy 0,0+dy,0+2∗dy,...,0+(k−1)∗dy.那么此时题目就酿成了,同时满意下面等式的 k k k的个数 ( k ∗ d x + s u m x i ) % ( 2 ∗ W ) = 0 ( k ∗ d y + s u m y i ) % ( 2 ∗ H ) = 0 (k*dx+sumx_i)\%(2*W)=0 \\ (k*dy+sumy_i)\%(2*H)=0 (k∗dx+sumxi)%(2∗W)=0(k∗dy+sumyi)%(2∗H)=0考虑到 s u m x i < 2 ∗ W , s u m y i < 2 ∗ H sumx_i<2*W,sumy_i<2*H sumxi<2∗W,sumyi<2∗H,以是我们可以化简上式:
k ∗ d x ≡ ( 2 ∗ W − s u m x i ) m o d ( 2 ∗ W ) k ∗ d y ≡ ( 2 ∗ H − s u m y i ) m o d ( 2 ∗ H ) k*dx\equiv(2*W-sumx_i) \;mod(2*W) \\ k*dy\equiv(2*H-sumy_i)\;mod(2*H) k∗dx≡(2∗W−sumxi)mod(2∗W)k∗dy≡(2∗H−sumyi)mod(2∗H)发现是一个同余式,同时模数并不是质数,以是考虑利用扩展中国剩余定理去解.回想一下扩展中国剩余定理的题目式子,是 x ≡ b i m o d a i x\equiv b_i mod\;a_i x≡bimodai诶有点不一样,我们此时的x前面有一个系数,此时会有人说了,我们直接将dx拿逆元除掉行不行,固然不行,因为我们此时的dx不一定和模数互质,以是费马小定理用不了,但是对于一个同余式,我们是可以利用扩展欧几里得解出一个关于x0的通式的(举个栗子,显然第一个同余式等同于 k ∗ d x + g ∗ ( 2 ∗ W ) = 2 ∗ W − s u m x i k*dx+g*(2*W)=2*W-sumx_i k∗dx+g∗(2∗W)=2∗W−sumxi) 而对于那个通式,我们会发现k的系数为1,符合扩展中国剩余定理的题目式,以是我们对上述两个式子先拿扩欧解出通式,然后再把通式转成同余式,然后用扩展中国剩余定理求那两个同余式.但是必要注意的是,扩展中国剩余定理只能求出 l c m ( 模数 ) lcm(模数) lcm(模数)范围内的唯一解,但是我们的 k k k是有大概大于这个 l c m lcm lcm,以是实际上这个解的个数得拿 k k k除一下模数求出真正的贡献(事实上此时的合法k序列是一个等差数列) 接下来是具体的代码部分:
E a s y Easy Easy版本: