BSGS(Baby steps giant steps)算法学习笔记

离散对数(Discrete Logarithm)问题是这样一个问题,它是对于模方程

a^x=b(mod prime),求满足条件的X,或者得出不存在这样的X

最暴力的思路,那么就是枚举x? 根据费马小定理,只需要枚举[0,p-1)

但是还是很大…我们不禁想到把x写成x=A*m+B的形式,m=ceil(sqrt(p))

因此有 a^{A\lceil \sqrt{p} \rceil + B} \equiv b \pmod p ,变形得到 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^{-B} \pmod p

然后预处理一边存到map中,从小到大枚举另一边看是否存在…

 

我们可以设 x=A \lceil \sqrt{p} \rceil - B,其中 0 \leq B < \lceil \sqrt{p} \rceil,  0 < A \leq \lceil \sqrt{p} \rceil + 1,这样的话化简后的方程就是

 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^B \pmod p

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

 

其实在m=sqrt(p)的时候你可能就有预感了…

BSGS算法的本质,就是个分块啊,而分块的本质就是暴力乱搞…所以BSGS看起来很高大上的算法不过是暴力乱搞2333

而BSGS的名字也很贴切…A的变化是giant step?B的变化是baby step? (纯属yy…但是我感觉这样想很好理解啊?

需要注意的是,这里介绍的是常规的BSGS算法,

前提条件是a和P互质

前提条件是a和P互质

前提条件是a和P互质

放一个板子好了,poj 2417

 

参考资料:

一个很多BSGS算法初学者的误区

扩展大步小步法解决离散对数问题

大步小步算法与扩展大步小步算法

BSGS算法学习小记(大步小步算法)

 

 

 

spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很方便得统计每个数出现的次数,update的时候,如果是1变成0,那么区间中不同的数的个数减1,如果是0变成1,那么区间中不同数个数+1

 

补一个在线的做法,可持久化线段树,其实思路和离线线段树几乎一样。

 

bzoj2002: [Hnoi2010]Bounce 弹飞绵羊 (分块)

http://www.lydsy.com/JudgeOnline/problem.php?id=2002

题意+思路: 同codeforces 13 E holes.

 

codeforces 13 E. Holes (分块)

http://codeforces.com/problemset/problem/13/E
题意:给你n个洞,进入某个洞后会跑到另一个洞,到了另一个洞之后又可能会继续到下一个洞,问你从一个洞进去,钻了几个洞才会出来,在哪个洞出来

n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]….

思路:分块大法好。具体见代码注释。以及。。。cin加速之后还是很慢。。。能不用就不用吧。

hdu 4638 Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。
思路:增加一个元素,如果它两边的元素都出现了,那么段数-1(相当于把两段连接起来合并成了一段),如果两边元素都没有出现,那么段数+1.反过来,减少一个元素时,如果两边元素都出现了,俺么段数+1(相当于把完整的一段断开成两段),如果两边元素都没有出现,那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000,所以判断某个元素是否出现开一个100000大小的布尔数组即可(我竟然傻逼得去用set….然后华丽丽得TLE了2333)

选区_019

 

hdu 5213 lucky (莫队算法)

http://acm.hdu.edu.cn/showproblem.php?pid=5213
题意:n个数,m个查询,每个查询由4个数l1,r1,l2,r2构成,询问分别从[l1,r1]和[l2,r2]中各取一个数,和为给定的常数k的方案数。

思路:首先分别由两个区间取数不好搞,我们可以用容斥原理对区间变换。这是这道题最关键的一步。

官方题解:这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A,B时的答案 用记号+表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]A=[l1,r1],B=[l2,r2],C=[r1+1,l21]容易知道(并没有很容易f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)f(A,B)=f(A+B+C,A+B+C)+f(C,C)f(A+C,A+C)f(C+B,C+B) 因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为O(msqrt(n))O(msqrt(n))

然后就是莫队算法的内容。值得一提的是,被拆成的四个子询问不必做四次莫队,可以合在一起,因为每一次询问对答案的贡献都不会受顺序影响,而且这样用时更短。

然后初始构造的时候用构造函数比赋值要方便许多。

还要记得多组数据记得清空各种数组。。。(因为忘记清空ans数组wa到死。。。)

最最关键的是,对于求两个数a+b==k这类问题(不一定是加,就是和两个数满足一个关系的时候),我们可以转换思维。a==k-b.也就是统计的时候是cnt[b]++,更新答案的时候,由于现在是b,我需要找有多少个a,也就是多少个k-b,所以是ans+=cnt[k-b];(要注意保证k-b>0)

 

 

codeforces 220 B. Little Elephant and Array

http://codeforces.com/contest/220/problem/B

题意:n个数,m个查询区间,对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。

思路:首先,a[i]很大。。。但是n最大才1e5…每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次,上莫队算法。

 

codeforces 86 D. Powerful array (莫队算法)

http://codeforces.com/problemset/problem/86/D

题意:Ks为区间内s的数目,求区间[L,R]之间所有Ks*Ks*s的和

思路:莫队算法,和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。

再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==

选区_016

 

 

(莫队算法的学习)bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose)

Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 5327 Solved: 2461
[Submit][Status][Discuss]
Description

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数L,R表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

【样例解释】

询问1:共C(5,2)=10种可能,其中抽出两个2有1种可能,抽出两个3有3种可能,概率为(1+3)/10=4/10=2/5。

询问2:共C(3,2)=3种可能,无法抽到颜色相同的袜子,概率为0/3=0/1。

询问3:共C(3,2)=3种可能,均为抽出两个3,概率为3/3=1/1。

注:上述C(a, b)表示组合数,组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

【数据规模和约定】

30%的数据中 N,M ≤ 5000;

60%的数据中 N,M ≤ 25000;

100%的数据中 N,M ≤ 50000,1 ≤ L < R ≤ N,Ci ≤ N。

中文题目,不解释了。
思路:分块+莫队算法。http://blog.csdn.net/bossup/article/details/39236275
这篇博客讲得很清楚。看完之后自己写的。。调了大概两个小时。。。?感觉有些理解了。
注意的是,如果最后分子为0,那么分母要赋值成1,而且分子为0的时候不要去求gcd…

 

 

hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391
题意:有 n 个点,每个点有一种颜色(可能相同),两种操作:1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。
思路:因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。

hdoj 1754 I hate it

http://acm.hdu.edu.cn/showproblem.php?pid=1754
题意:给定一个区间,有m组操作,操作可以是改变单点,或者查询区间最大值。对于每组查询,输出。
思路:分块。这篇博客说得很不错。http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html

codeforces #319 div 2 E C. Points on Plane (分块)

初识分快.

引一段题解:

Let’s split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let’s number them from left to right. We’re going to pass through points rectangle by rectangle. Inside the rectangle we’re going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it’s odd.

Let’s calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we’re passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we’re spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.

The complexity is O(n * log(n))

 并不会做,看了题解写的,感觉好神奇…

然后加深了sort的cmp函数的理解...

原来还可以这么写.

有点开心,因为觉得解法有点美.