-
二次剩余理论的数学基础
二次剩余理论在密码学中占有重要的地位，很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”，可见其重要性。这里列举关于二次剩余的常见定理，方便日后查阅。 定义 对于奇素数p，p和d互素，如果$x^2 \equiv d\ mod\ p$，那么称d是模p的二次剩余，否则称称d是模p的二次非剩余。记模p的二次剩余的全体为$QR_p$，模p的二次非剩余的全体为$QNR_p$。 定理(1) 模p的既约剩余系中，二次剩余与二次非剩余各占一半：$|QR_p|=|QNR_p|=…
-
概率dp专题整理(2/2)
LightOJ 1027 A Dangerous Maze: 预先求出递推式，最后通过公式直接计算。 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> using namespace std; int gcd(int a, int b){ if (b ==…
-
数论基础专题小结
这个专题很杂，牵涉到很多数学公式和一些优化方法，还是要根据不同的题目来积累经验。 LightOJ 1282 Leading and Trailing: 这道题牵涉到求一个大数的前几位和后几位的方法，前者主要是通过对数进行处理，后者通过快速取模。 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> using…
-
概率dp专题整理(1/2)
概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活，没有固定的范式，没有模版可言。正如大部分的dp题目一样，思考量远大于代码量。需要注意的是，一般求概率是正推，求期望是逆推。 LightOJ 1030 Discovering Gold: #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int a[10…
-
区间dp专题小结
区间DP是一类在区间上进行动态规划的最优问题，一般是根据问题设出一个表示状态的dp，可以是二维的也可以是三维的，一般情况下为二维。然后将问题划分成两个子问题，也就是一段区间分成左右两个区间，然后将左右两个区间合并到整个区间，或者说局部最优解合并为全局最优解，然后得解。 这类DP可以用常规的for循环来写，也可以用记忆化搜索来写。一般情况下记忆化搜索的代码比较好写，所以一般都用dfs来代替获得dp值。然而说到底，这只是一种思想，具体的代码根据题目的不同差别很大，而且有很多需要考虑的细节。 POJ…
-
斜率优化dp专题小结
斜率优化dp是一种通过构造斜率表达式，用维护凸包的方法来去除多余的点以减少算法复杂度的方法。通常可以将问题规模减小一个维度，从而提高运行效率。 这个算法的关键是将dp的状态转移方程进行转换，比如对于如下状态转移方程： $$dp[i]=Min(dp[j]+M+(sum[i]-sum[j])^2),j\in [1,i),i\in [1,n]$$ 如果直接dp那么复杂度将会是(O(n_2)),某些情况下就会显得效率不够。这时候就可以用斜率dp进行优化，将其优化到$O(n)$。 首先我们需要将状态转移方…
-
LaTeX概述和Linux下的安装
简述 看来开个博客真的是能学到东西的，有些问题只有写下来才会明白这的确是一个问题。比如，在博客或者论文里打公式的问题。本来以为这根本就不是个问题，结果才发现这的确是一个大大的问题，硬是扯出了一个新的语言---LaTex语言。 LaTeX，音译为“拉泰赫” /‘lɑtɛk/，实际上应该确实的写成“LaTeX”。绝对不要改变任何一个字母的大小写，以免和“latex”（胶乳）一词相混。 然而说穿了这个也不能算是一种语言，只能说这是一种基于ΤΕΧ的排版系统，由美国计算机学家莱斯利·兰伯特（Lesl…
-
LaTeX中一些特殊数学公式的编写
前言 一般情况下，在编写数学公式的时候，符号表就能满足我们的需求。但是很多情况下，当我们书写一些比较复杂的行间公式时，这点符号就显得捉襟见肘了，一下就整理一些常用的特殊数学公式 上标和下标 $\text{\overset{}{}}$ 这个东西后面接两个参数，第一个参数表示想加上标，第二个参数表示施加的对象,如果不加大括号，那么默认是把最近的一个元素作为下一个参数，比如 $$\text{\overset{up}{base}}:\overset{up}{base}$$ $\text{\und…
-
大组合数取模的Lucas定理
一般情况下，我们计算大组合数取模问题是用递推公式进行计算的： $$ C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p $$ 其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加$O(mn)$，在实践中不适用。当这时候就需要Lucas定理进行快速运算: $$ C_n^m=\prod_{i=0}^{k}C_{n_i}^{m_i}\ mod\ p $$ 其中： $$ m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0 $$ $$ n=n_kp…
-
Garbled Bloom Filters算法简述
简述 Garbled Bloom Filters（GBF） 算法是Bloom Filters （BF）算法的变形，并且结合了Shamir的信息分享算法，更好的解决了hash冲突的问题其形式上是将Bloom Filters算法中的BitSet数组转换成了字符串数组，数组中的每一个字符串长度为安全参数$\lambda$，可以通过调节这个参数来获得想要的安全性。该算法同Bloom Filters 一样，是一种有一定容错率的hash算法，对于存在于集合中的元素查询返回的值总是true，而对于不在集合中…