离散对数（Discrete Logarithm）问题是这样一个问题，它是对于模方程 a^x=b(mod prime)，求满足条件的X，或者得出不存在这样的X 最暴力的思路，那么就是枚举x? 根据费马小定理，只需要枚举[0,p-1) 但是还是很大...我们不禁想到把x写成x=A*m+B的形式，m=ceil(sqrt(p)) 因此有 ，变形得到 然后预处理一边存到map中，从小到大枚举另一边看是否存在... 我们可以设 ，其中 , ，这样的话化简后的方程就是 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出 …

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： /* *********************************************** Author :111qqz Created Time :Fri 16 Sep 2016 11:34:32 PM CST File Name :code/spoj/dquery.cpp ************************************************ */ #include <cstdio> #include <cstring> …

http://www.lydsy.com/JudgeOnline/problem.php?id=2002 题意+思路： 同codeforces 13 E holes. /* *********************************************** Author :111qqz Created Time :2016年02月21日 星期日 02时29分39秒 File Name :code/bzoj/2002.cpp ************************************************ */ #include <cstdio> #include <cstring> …

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来 n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i].... 思路：分块大法好。具体见代码注释。以及。。。cin加速之后还是很慢。。。能不用就不用吧。 /* *********************************************** Author :111qqz Created Time :2016年02月20日 星期六 23时48分28秒 File Name …

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大小的布尔数组即可（我竟然傻逼 …

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)的值 不妨假 …

http://codeforces.com/contest/220/problem/B 题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。 思路：首先，a[i]很大。。。但是n最大才1e5...每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。 /* *********************************************** Author :111qqz Created Time :2016年02月14日 星期日 00时47分18秒 File Name :code/cf/problem/220B.cpp …

http://codeforces.com/problemset/problem/86/D 题意：Ks为区间内s的数目，求区间[L,R]之间所有KsKss的和 思路：莫队算法，和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。 再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多== /* *********************************************** Author :111qqz Created Time :2016年02月13日 星期六 23时17分58秒 File Name :code/cf/problem/86D.cpp …

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，他有多 …

http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。 /* *********************************************** Author :111qqz Created Time :2015年12月15日 星期二 15时00分34秒 File Name :code/hdoj/4391.cpp …