我们用数学方式来重新定义计算机里面的运算，因为内存是有限的，所以我们在计算机当中 存储数据的时候，这些数据都是有范围的数，所以所有的运算都是建立在模数上的，例如加法成了 模加。a+b成了（a+b）%mod。 为了让减法跑的更快，我们把减法丢掉了，于是这个世界只有加法了。减法成了加一个负数。 负数又是怎么定义的呢？如果x=-1，我们可以这样来存储（0-1+mod）%mod=mod-1 于是我们把负数也映射到了新的正数上。 由于模加也满足加法的交换率结合律等等优良性质。很明显，对于负数-x和-y我们存的是mod-x 和mod-y，于是经历模加（-x+-y）%mod=（mod-x+mod-y)%mod这显然是正确的。
由于计算机内部memery与 processor之间的速度差距过大，导致计算机整体速度降低，memery拖慢了速度。于是人们想出 了一个办法来解决他。缓存Cache诞生了。 Cache相对于Memery来说，速度快了很多，速度快意味着造价高，容量小，这是代价，我们没有那么多钱来用Cache来当作 Memery，于是我们尝试，让他作为Processor与Memery的中介。 为什么要Cache，因为Memery太慢了，用Cache的话，容量问题很显然，Cache很小，没有Memery那么大。但是我们的初衷 是什么，用Cache去代替Memery，但是，Cache这个家伙小啊，我们不可能把一个大的东西放进一个小的盒子里面。 这是缓存 面临的最大问题。 重新思考计算机的运转，指令是一条一条执行的，当计算机运转的时候，CPU关心的不是整个Memery，他只要他的东西，他所需要的 只是局部的信息。于是我们开始思考，既然Cache没有Memery那么大，那我们就构建一个一对多的映射，一个Cache地址，去对应 多个Memery地址，问题似乎解决了，是的Cache就是那样工作的。 一对多的问题不好解决，你怎么知道一对多的时候，对应的是哪一个呢？我们是这样子解决的，把Memery的地址映射 Mx到Cache的地址Cx，这是唯一的，但是Cache是一对多啊，我们假设是一对四，然后我们在Cache的地址所指向的位置添 加一个标记，用来指示他目前对应是哪一个Memery地址，不妨说他目前对应的是第三个Memery。现在问题基本解决了。 例如： 有四个Memery地址Mx1，Mx2，Mx3，Mx4，都映射到了Cx，但是Cx上有一个标记，标记说Cx目前存的值等于Mx3 存的值。这样就完美解决了映射的问题。但是新的问题来了，无法逃避，Cache毕竟没有Memery那么大，我现在 要访问Mx1，结果我找到了Cx，Cx却告诉我他现在存的东西不是Mx1，而是Mx3，怎么办？？ 没办法，这种情况叫miss，只能从Memery找了，我们是这样做的：把从Memery把Mx1以及他附近的其他东西搬过来 搬到Cache，然后更新Cache的标志。回到刚才的例子，也就是把Mx1以及他附近的其他信息的东西搬到了Cx上 然后改掉Cx的标记，说Cx现在不是Mx3了，他现在与Mx1一起了。 如此复杂的操作，真的回使得计算机变快吗？是的，平均性能上提高了，因为Cache和Memery速度差异巨大。不过杨老师曾指出一个 反例，他说，你要是有个恐怖分子，不用我们的Cache，当Cx与Mx1一致的时候你要用Mx2，当Cx变得根Mx2相同了，你 又要用Mx1，那岂不是凉凉？好像确实是这样子的。 为什么说是平均性能的提高呢？有两点，memery使用的时间局部性和空间局部性，当你使用了一个Memery的地址 后，你在不久的将来可能还会使用他 ，你也有肯能使用他附近的其他信息。所以我们把和他相关的东西一股脑都放进 Cache就可以了，但是放多少呢？这个问题，先辈们已经通过统计得出来结论。我们不必关心。
之前我们谈到的只是口糊，具体实现的时候，不是一个地址对应一个地址，而是一块对应一块（block）， 我们曾谈到，空间局部性，所以说这里不要一个地址对应一个地址的玩了。我们引入block。也就是说 我们把地址Mx1_begin 到Mx1_end这一整块的地址映射到Cx_begin到Cx_end ， 然后放一个标记就可以了， 这样的优点很多，比如说省掉了很多标记的记录。。。等等的 Cache的地址分为三大块，tag,index,和offset offset指的是一种偏移量，我们之前说过，Cache里面分了很多个block，每一个block都是一个整体，所以 当我们找到了正确的当block当时候，offset用来指向block里面的详细地址。显然，block里面有多少种地址 offset就有多少种值。举个例子，当block是64B的时候，他一共有2^6个byte，我们计算机寻址所关心的只是 哪一个byte，（一般而言，四个byte为一个words）所以我们的offset需要有6个bit，才能恰好指向这2^6个 byte。于是在这种情况下offset为6位 index指向我们要找的哪一个block，见杨老师的图 
很明显，如果在上述条件下我们的Cache一共有64KB的话，那我们就有 64KB/6B=2^10个block，于是index就是10位的了，可是有一些Cache，特别的有趣，它允许多对多。这就很 头疼了，不过这确实是个好办法。有一定的优点。 多对多是个什么情况呢？类似于这样,有Cx1 Cx2，Mx1，Mx2，Mx3，Mx4，他们很乱，四个Mx都可能映射到 Cx1，也都可能映射到Cx2，注意对比之前的一对多:有Cx，Mx1，Mx2，Mx3，Mx4,四个Mx都可能映射到Cx 多对多多优点的话，不好说，其实是我不知道。这种多对多的骚操作，实现起来更复杂了，他叫n-way set-assoc. 中文名n路集相关。很shit，很神奇。下面是二路集相关（还是杨老师的）. 
在n路及相关的情况下，index又叫做set，这是他的新名字，这个时候他指向一堆block，换句话说，一堆block共用 一个index。于是，如果刚刚的64KBCache是二路集相关的话，他的index是9位，因为一个index可以指向两个 block。 至于tag，我不是很清楚了。应对考试的话，他的位数用PPA(Physical Page Address )减去index和offset就得到了。 最后剩下的一个是Data Cache entry 他的大小等于Valid bit, Dirty bit, Cache tag + ？？ Bytes of Data， 有这些一起组成。Valid bit 一般是一位，他的作用是用来指示这个block是否有用，为什么会没有用呢 我们想到，程序总有启动的时候，当程序刚刚启动的时候，block是无效的，它里面的数据存在，但是 数据却不一定和Memery保持一致。这个问题无法避免，但是可以通过Valid bit解决。Dirty bit是一种懒惰 标记，一般的树形结构，例如线段树，spaly，以及各种可持久化数据结构里面都用这种东西。他用来表明 一种懒惰性，因为Memery慢，因为Cache是用来代替Memery的，当我们读取数据的时候，没有他的用途 单当我们更新数据的时候，我们一定要立即更新Memery吗，不是的，我们可以只更新Cache的block，等 到miss发生的时候，在把它们一起写入Memery即可，所以他叫脏位。是一位。Cache tag就是我们之前说的 标记，用来防止一对多的情况下的那个标记，他等于前面我们算出来的tag的大小。最后一个是Bytes of Data 他恰好等于block的大小，例如64KB的那个Cache，他的大小位64KB=64*8bits=512bits，于是总大小为 1+1+21+512=535bits
浮点数很神奇，Prof. Kahan是个鬼才。可以说浮点数的诞生很大程度上推动了计算机的发展。
在计算机中，浮点数主要以科学计数法存储，其科学计数法底数为2，于是一般而言：浮点数分为三个部分，符号域（Sign），指数域（Exponent），尾数域（Fraction）。 分别对应科学计数法的有效数字的符号，有效数字的指数，有效数字的小数部分。
为了让浮点数的比较能够由整形的比较器完成，其指数采取移码来表示，（移码和补码只有符 号位相反，其余都一样。对于正数而言，原码、反码和补码都一样；对于负数而言，补码就是其绝对值的原码全部取反，然后加1（不包括符号位）） 形象地来来说移码是原码的移动，在数值上移码等于原码减去2^(k-1)-1,k是位数。但是并不是所有的浮点数都采取此种表示方法。有一小部分浮点数的指数域， 与之不同，我们在后面说。
为什么叫尾数域，而不叫有效数字域，其实很容易想到二进制的科学计数法的整数部分必然是1，于是这个1被省略掉了，计算机不存储他。
如果我们真的像刚刚分析的那样，结束了浮点数的定义，会有一个问题，那就是0不见了，并且靠近0的一小部分有一个巨大的gap，我们后面在证明这个gap存在，于是我们的浮点数设计失败， 但是Prof. Kahan想到了一个解决方法，他发现当指数域的指是一个最小的负数的时候，当前浮点数所表示的数非常小，与0很接近，并且那一部分的精度非常高，精度高，但是靠近0的地 方有一个巨大的gap，怎么办？他考虑到，用一部分高精度的丢失换取gap的填充。也就是说，当指数部分是最小的负数的时候，我们不采取科学计数法了，当指数域为最小的负数 的时候，我们把尾数域看作一个无符号整形，他会可以表示一个整形区间，我们hash掉这个区间，让他来表示gap即可。后面来证明这个做法的可靠性。
既然花了一部分指数域做了一个0，为什么不来一个无穷大呢？于是Prof. Kahan创建了无穷大的表示方法，当指数部分是最大的正数的时候，此数字表示无穷大怎么样？若符号域为正，我们表示 正无穷，若符号位为负，我们表示负无穷怎么样？于是我们发现我们思维的漏洞了，刚刚的0，岂不是有+0与-0？是的就是有，等下我们证明他的合理性。 再回到无穷上，我们与0的表示做对比，发现了指数固定的时候可是一个区间啊，有很多的无穷大，是啊，我们要不了这么多无穷大，那怎么办呢？于是Prof. Kahan说多余的他们都叫做 nan，意味着not a number。我们依然在后面证明这个做法的优点很大很大。
这些都是理论指导，实际上浮点数到底怎么存的呢？见图 （照片丢了，我也没找到）
给出特例，对于单精度浮点而言，我们先考虑浮点数的表示精度问题，如果放开指数不谈，令指数为0 ，那么我们可以表示出大致区间[1,2)，如果指数为1，我们又可以表示区间[2,4) 等等。。。 我们仔细分析，这里的区间长度是变化的，但是表示这段区间的数的数量是固定的。显然一个问题出现了，我们可以大胆猜测，指数越大，精度越低，我们把几个区间都写一下 当指数为-2 -1 0 1 2 分别表示了区间[1/4，1/2）[1/2，1）[1，2）[2，4）[4，8），是的，区间长度递增，猜测正确。
然后我们还发现，精度是有规律的，同一个区间的精度固定，因为尾数是平分区间的，不同区间的精度怎么样呢？我们来看看，[1，2）的精度是[2，4）的精度的两倍， 于是我们得到精度的详细情况，离0越远的区间，精度越低，且是他的前一个区间的精度的一半，（定义一个区间的前一个区间为与之相邻的离0更近的区间）
我们再来考虑最小的正浮点数，在什么地方，对的，就是\(2^{-127}\)，我们假设这个数为x，他右边部分的精度达到了\(\frac{2^{-126}-2^{-127}}{2^{23}}=2^{-150}\)在x的左侧呢，哈哈一个gap，他与0之间相隔\(2^{-127}\)，\(2^{-150}\) 和\(2^{-127}\) 区别可大了，负数那边也是样的。
如果考虑不要精度为\(2^{-150}\)的区间的，用它来填补gap，代价是什么？会不会导致浮点数优秀的精度递增模式被打破呢，很遗憾不会。我们来计算，如果考虑丢弃此区间 换来的最小的正科学计数法所表示的浮点数的值为\(2^{-126}\) ，因为区间\([2^{-127} ，2^{-126})\) 拿走了，这时候他右边的精度为\(\frac{2^{-125}-2^{-126}}{2^{23}}=2^{-149}\)，emm，还行，我们来计算那个究极大gap的精度，\(\frac{2^{-126}}{2^{23}}=2^{-149}\)奇迹出现了，精度一摸一样，精度的优秀性质基本得到了保留，这种做法使得从0到正无穷的过程中没有变小。很神奇。
为什么要搞+0和-0，这两者不是相同的吗？是的他们是相同的，+0.0==-0.0 返回值是true ，这个时候我们开始思考0的意义，0到底是什么，我们参考无穷大，重新定义0，+0.0代表正无穷小 -0.0代表负无穷小，这才是他们本质上的意义，sorry，我们又把0给弄没了。这次我们不把它找回来了，+0.0和-0.0共同组成了0。为什么要这样做，还有一个额外的点，我们的数域里面可是有正负 无穷大的，我们，要搞在浮点数里面搞一套新的，特别的运算法则，极限的运算。这是他的另一个点。
为什么要搞nan，这是给程序员用的，哈哈哈哈哈哈嗝，哈哈嗝，用来debug，但笔者不太懂一点，为什么要搞那么多nan呢，指数最大值的时候，除了正负无穷，其他的数字都是nan，为什么要这么复杂呢？ 限于水平，笔者大致猜到了，极有可能，不正确的运算直接会算出nan，这会加速浮点数的运算，（也就是说，不需要我们自己去做判断是否运算合法）（也就是说浮点数的运算不是封闭的，错误 或者不合法的运算会直接算出nan，而不是计算机去判断运算是否合法）这只是笔者的一个猜想。
若x为nan ，那么x==x为假 x不管之后怎么运算，得到的永远是nan +0.0 == -0.0 为真
让你用lg的时间复杂度求下面这东西(n<1e18)
$$ \[\begin{aligned} &\prod_{i=1...n}{(2i-1)} \%2^{64}\\& suppose\quad that\quad f(x,n)=(2x+1)(2x+3)(2x+5)...(2x+2n-1)\%2^{64}\\& then \quad the \quad 0th \quad item \quad of \quad f(x,n) \quad is \quad answer\\& we \quad can \quad try \quad to\quad calculate \quad f(x,n) \quad by \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor) \\& let \quad y=x+n\\& then \quad f(y,n)=(2y+1)(2y+3)(2y+5)...(2y+2n-1)\%2^{64}\\& so \quad f(x+n,n)=(2x+2n+1)(2x+2n+3)(2x+2n+5)...(2y+4n-1)\%2^{64}\\& Surprisedly \quad we \quad find \quad that \quad f(x,2n)=f(x,n)*f(x+n,n)\\& which \quad means \quad we \quad can \quad calculate\quad f(x,2n)\quad by\quad f(x,n) \quad easy\\& \\& becase \quad we \quad can \quad calculate \quad f(x+n,n)\quad by \quad f(x,n) \\& but \quad we \quad can't \quad calculate \quad it \quad faster \quad because\quad of\quad the\quad huge\quad numbers \quad of \quad item\\& considering \quad that \quad we \quad need \quad mod \quad 2^{64} , we\quad can \quad reserve \quad the \quad items \quad with \quad index \quad less\quad than\quad 64\\& because \quad the \quad useful \quad information \quad is \quad the \quad 0th \quad item \\& and \quad in \quad f(x,n)\quad when \quad the\quad index\quad of\quad x \quad is \quad larger \quad than\quad 63 ,the \quad coefficient \quad of \quad it \quad must\quad divisible\quad 2^{64}\\& it \quad has \quad no \quad contribution \quad to \quad answer \quad and \quad f(x+n,n)\\& so \quad we \quad can \quad solve \quad it \quad by \quad this \quad way \\& for \quad every \quad polynomial \quad we \quad reserve\quad the \quad first \quad 64\quad items \quad of\quad x \\& and \quad then \quad calculate \quad f(x,n) \quad by \left\{\begin{matrix} \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor)*f(x+\left \lfloor \frac{n}{2} \right \rfloor,\left \lfloor \frac{n}{2} \right \rfloor)\quad if \quad n\%2=0\\& \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor)*f(x+\left \lfloor \frac{n}{2} \right \rfloor,\left \lfloor \frac{n}{2} \right \rfloor)*(2x+2n-1) \quad if \quad n\%2=1 \end{matrix}\right. \\& and \quad we \quad can \quad get \quad the \quad answer \quad no \quad more \quad than \quad lg \quad times \quad recursion\\& because \quad of \quad the \quad 64 \quad items \quad only \quad and \quad we \quad don't\quad care \quad the \quad higher \quad items ,\\& it \quad is \quad very \quad fast \quad to \quad get \quad f(x,n)\quad by \quad f(x+n,n) \\& so\quad the\quad total\quad time\quad complexity \quad is \quad O(lgn) \end{aligned}\]$$
假设f(x,n)=(2x+1)(2x+3)(2x+5)...(2x+2n-1)%64
然后这东西的0次项系数就是答案
我们尝试通过f(x,n/2)来求f(x,n)
令y=x+n
则f(y,n)=(2y+1)(2y+3)(2y+5)...(2y+2n-1)%64
所以f(x+n,n)=(2x+2n+1)(2x+2n+3)(2x+2n+5)...(2x+4n-1)%64
我们惊讶地发现了f(x,2n)=f(x,n)*(fx+n,n)
这意味着我们可以通过f(x,n)来求f(x,2n)因为我们可以通过f(x,n)求出f(x+n,n)
很遗憾的是这些东西项数太多了
考虑到我们要的是模上2^64的答案，我们可以只保留前64项
因为有用的只有0次项，但是在f(x,n)转移到f(x+n,n)的时候也只有前64项有效，因为大于指数64的项，他们前面的系数一定整除2^64次方，
于是我们就有了做法了
我们保留前64项
...
时间复杂度为lg级别
这一类做法，通常不是很好想，但是很多题目都能这样做。
有一个超级大的背包，物品的价值等于容量，但是物品只有8种容量分别为1-8 给你每个物品的数量ai，和背包总容量w，问能背走的最大价值是多少 w<1e18;
设dp[i][j]为前i类物品，背满j是否可行,复杂度\(O(8\times n)\)
状态过多，状态冗余，可能存在某些能合并的状态
840是1-8的数的lcm, 于是我们可以把背包W分为 \(840k + (W-840k)\) 两个部分。 且后一部分小于\(840\times8\)
先谈谈唯一分解
我们对每一种放法 ，进行唯一分解:
先把每一类容量相等的物品唯一分解为两部分, 第一部分的总容量为840的一个倍数，第二部分总容量小于840
比方说某种方法选择了1000个1，3000个2，5000个3...
那么我们将其唯一分解为:
\(1\times840+160个1\)
\(7\times 420+ 60个2\)
\(17\times280+240个3\) 然后把每类容量为840的倍数的那一部分合在一起: 于是成了\((1\times840+7\times420\times2+17\times280\times3) + 160\times1+60\times2+240\times3+0\times4+0\times5+...\) =\(840\times25 + 160\times1+60\times2+240\times3+0\times4+0\times5+...\) 这就是唯一分解。
然后我们考虑，为什么这一题不能使用，背包，因为容量大？物品多？是的，
但是这些都只是表面上的。我们深入思考，能不能把某些没有意义的方案合并到一个状态里面呢？
我们不要设dp[i][j]表示什么前i类物品装满容量j是否可行这样的状态。因为这是\(8\times n\)级别的状态 我们根据唯一分解，设dp[k][i][j]代表背包的第一个部分容量为840*k,第二部分为前i类物品装满容量j 若值为1，代表可行，否则不可行。
显然k<n/840,i<8, j<840*8
现在的状态数为(n/840)*8*(840*8)
状态数目变多了。转移也更加复杂，看似此状态还不如朴素做法。
这一点应该是很容易想到的。这个dp[k][i][j],具有单调性，一定存在某个值t, 使得dp[k][i][j]的值在i和j固定，k<=t的时候全为1，在k>t的时候全为0
显然这个t是最优的
我们换一种状态的设法，设dp[i][j]为只取前i类物品的方案的唯一分解下，不考虑背包容量上限，第二部分容量为j，第一部分的k能取到的大值。
dp[i][j] ---> dp[i+1][j+t*i] t是选取的数量，j+t*i<8*840
这样的做法就已经很快了。
如果一个在数字上的计数问题只与数位和数的大小有关的时候 我们可以尝试用数位dp来解决。最经典的就像不要62那道题。
我们常常设dp[val][len][limit][lead]来表示以val开头 数位长度剩余len(包含val)，limit表示数有没有上限,后面发现这一维度没有作用 。lead表示val及以前是否含有前导数，来特判某些跟前导0有关的题目
1 | ll dfs(int*num, int n, int pre, int pos, bool limit, bool lead){//try to fill the pos bit |
http://codeforces.com/contest/617/problem/E
给长度为n的序列，给数字k，给q次询问,每次询问给出[L,R],求这个区间内有多少个连续区间的异或和等于k。
题解
预处理前缀异或和，化简区间为两个点异或值为k，再来莫队。
hdu5213，给你序列a，其长度为n，给你q个询问，每次询问给两个不相交的区间，求a[i]+a[j]=k的方案数，i属于第一个区间，j属于第二个区间。
(1≤N≤30000) (2≤K≤2*N) (1≤ai≤N)(1≤M≤30000) (1≤Li≤Ri<Ui≤Vi≤N)
题解
化简多区间为单区间询问，再来莫队
fzu2226， 给你长度为n的序列，定义第i个元素和第j个元素间的距离dis(i,j)=abs(i-j) 。给q个询问，每次询问一个区间[l,r]，要求你求出一对数字(i,j)(l<=i<=j<=r),使得a[i]=a[j]并且dis(i,j)最大，由于这样的数对可能有多个，因此答案只要输出dis。
N<=10^5 Q<=10^4 1<=a[i]<=10^3 1<=l<=r<=n
题解
莫队的时候，维护区间中每个值出现的最左下标和最右下标。
hdu4638， 给你一个长度为n的序列，m个询问，每次查询给一个区间，我们来划分这个区间，对于划分出的任意一个子区间，他的所有元素构成的集合所包含的数必须是一段连续的区间，然后定义区间的代价为区间长度的平方，定义划分的代价为划分结束后所有划分出的子区间的代价的和，询问此代价最高时的划分出的子区间的个数。
题解
可以证明，划分唯一，我们把划分操作看成切割原区间，定义划分的操作为切割点的位置的集合，若两个划分不一样，我们对这两个划分操作切割点集取交集，交集构成新的划分，此划分优于前两个划分。于是按照能合并就合并的贪心，我们可以找的最优划分。考虑莫队，当区间变化的时候：添加一个数，如果他左右的数字都存在，显然段数-1 若左右存在某一个，段数不变，若左右均不存在，则段数+1 ，删除同理。
hdu4676，给你一个排列，q个区间询问，求$_{Li<jR}gcd(a_i,a_j) $
题解
反演出结果后，直接莫队，对新加进来的数，枚举他的因子，计算莫队区间的变化。 \[ \begin{aligned} &n=id(n)=(1*\varphi)(n)=\sum_{d|n}\varphi(d) \\&\sum_{L\leq i<j\leq R}gcd(a_i,a_j) \\=&\sum_{L\leq i<j\leq R}\sum_{d|gcd(a_i,a_j)}\varphi(d) \\=&\sum_{L\leq i<j\leq R}\sum_{d|a_i}\sum_{d|a_j}\varphi(d) \\=&\sum_{d}\varphi(d)*C_{\sum_{i=L}^{R}[d|a_i]}^2 \end{aligned} \]
DFS计算最大团
1 |
|
BX正在进行一个字符串游戏，他手上有一个字符串L，以及其他一些字符串的集合S，然后他可以进行以下操作：对于一个在集合S中的字符串p,如果p在L中出现，BX就可以选择是否将其删除，如果删除，则将删除后L分裂成的左右 两部分合并。举个例子，L='abcdefg' , S={'de'}，如果BX选择将'de'从L中删去，则删后的L='abcfg'。现在BX可 以进行任意多次操作（删的次数，顺序都随意），他想知道最后L串的最短长度是多少。
|L|<=150
|S[i]|<=20
|S|<=30