wcwswswws的日记

wcwswswws

baby-step-giant-step

    Nov的codechef只做了4题……真悲剧……

     LuCKYDAY的意思是这样的:给一个数据列s[1]=s,s[2]=b,s[i]=(x*s[i-1]+y*s[i-2]+z) mod p,p是质数且p<10007。给定区间[l,r],求l<=k<=r使s[k]=c的个数。
      这题我写了个p^2的裸的找环的,构造了一个将近10^8的环和20000组询问,两组时间我最后优化到只要6s多就行了,所以我估计那些最后花了将近20s的就是写的相当完美的了。
      其实这题标准的做法是借鉴了 Baby-step giant-step 策略。wiki上说的很详细了我也就不多说了。这题我们可以简化:求出环的大小,以及环中每个c的位置。这里只讨论x,y均不等于0的情况。定义向量f(i)=(s[i],s[i+1],1)和转移矩阵A,使得f(i+1)=A * f(i)。因为所有数都是对P取模的,讨论一下就知道环中所有元素都有唯一前驱和后继的,所以f(1)必定是环中的一个点,环的大小就变成求f(k+1)==f(1)的最小k,这与第2个问题是相似的。
     由题设知f(k+1)=A^k*f(1),设k=i*m-j,其中m为环的长度的平方根(本题为p),0<=j<p,这样就变成了(A^m)^i*f(1)=A^j*f(k+1)。对于每个j的
A^j*f(k+1)可以先存下来(这里只要算p次),再计算等式左边 i 从1到p变化的结果(因为环最长为p^2),满足最小的那个 i 就是我们需要的,i*m-j就是我们要求的环的大小。其他问题就都好解决了。
        

posted on 2011-11-12 21:58 世界厕所所长 阅读(267) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理