Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 浮点数很神奇，Prof. Kahan是个鬼才。可以说浮点数的诞生很大程度上推动了计算机的发展。 浮点数的概况​ 在计算机中，浮点数主要以科学计数法存储，其科学计数法底数为2，于是一般而言：浮点数分为三个部分，符号域（Sign），指数域（Exponent），尾数域（Fraction）。 分别对应科学计数法的有效数字的符号，有效数字的指数，有效数字的小数部分。 浮点数的指数域​ 为了让浮点数的比较能够由整形的比较器完成，其指数采取移码来表示，（移码和补码只有符 号位相反，其余都一样。对于正数而言，原码、反码和补码都一样；对于负数而言，补码就是其绝对值的原码全部取反，然后加1（不包括符号位）） 形象地来来说移码是原码的移动，在数值上移码等于原码减去2^(k-1)-1,k是位数。但是并不是所有的浮点数都采取此种表示方法。有一小部分浮点数的指数域， 与之不同，我们在后面说。 浮点 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 让你用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 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 大范围贪心，小范围暴力这一类做法，通常不是很好想，但是很多题目都能这样做。 例题有一个超级大的背包，物品的价值等于容量，但是物品只有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… ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 常见数位dp如果一个在数字上的计数问题只与数位和数的大小有关的时候 我们可以尝试用数位dp来解决。最经典的就像不要62那道题。 数位dp状态我们常常设dp[val][len][limit][lead]来表示以val开头 数位长度剩余len(包含val)，limit表示数有没有上限,后面发现这一维度没有作用 。lead表示val及以前是否含有前导数，来特判某些跟前导0有关的题目 123456789101112131415161718ll dfs(int*num, int n, int pre, int pos, bool limit, bool lead){//try to fill the pos bit if(pos==n)return 1; else{ if(!limit&&dp[pre==6][num[pos]][n-pos] ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 例题1http://codeforces.com/contest/617/problem/E 给长度为n的序列，给数字k，给q次询问,每次询问给出[L,R],求这个区间内有多少个连续区间的异或和等于k。 题解 预处理前缀异或和，化简区间为两个点异或值为k，再来莫队。 例题2hdu5213，给你序列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) 题解 化简多区间为单区间询问，再来莫队 例题3fzu2226， 给你长度为n的序列，定义第i个元素和第j个元素间的距离dis(i,j)=abs(i-j) 。给q个询问，每次询问一个区间[l,r]，要求你求出一对数字(i,j)( ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial DFS计算最大团 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;const int maxn=105;bool edge[maxn][maxn]; int vertn; //int dfs_ans,found,mcp[maxn],suf[maxn][maxn]; // dfsvoid dfs(int d){ // begin with d =1 which means choose one point if(suf[d][0]==0){ if(dfs_ans<d) { ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 题意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 题解设置dp[i][j][k][t]代表L的子串L[i,j]，能否实现删除之后，可以匹配S中第k个串的前t个字符。 转移的时候 若匹配成功时，考虑第j位，若还在串中，且有L[j]==S[k][t],则可以由dp[i][ ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 题意给你两个串s,t和一个数k，询问是否存在s的k个不重叠子串按原顺序排列后能组成 t, 数据范围$|s|<1e5$,$|t|<1e5$,$k<100$,时间30s 题解设状态$dp1[i][j]$代表串$s$从$s[1]$匹配到$s[i]$的时候选择了$k$个不重叠子串后，能够匹配到t串到最远位置。 设状态$dp2[i][j]$代表串s从$s[1]$匹配到$s[i]$的时候选择了$k$个不重叠子串且最后一个子串以$s[i]$结尾后，能够匹配到t串到最远位置。 根据定义$dp1[i][j]=max(dp2[t][j]), \forall t<=i$，于是简单的写出了转移式子：$dp1[i][j]=max(dp1[i-1][j],dp2[i][j])$ 复杂的是$dp2[i][j]$不好得到，根据定义，$dp2[i][j]$一定会选择$s ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 前言本文力争用理性分析的手段，来推测此算法发明者的思维过程， 尝试感受其在设计此算法的时所展现出的思维方式， 力求用数学证明的手段，尽可能多的为读者证明相关结论，建议有其他自动机学习的基础，最好已经学会AC自动机和回文自动机，后缀自动机很难，他 和其他自动机不一样，它的状态更加复杂，一个算法的创作过程很 复杂，学起来当然会感到很难。强烈建议看陈立杰的ppt，看一遍肯定看不懂，仔细看，一遍看不懂看多遍，第一次可能只能看懂几面，第二次可 能就能看懂到十几面了，慢慢的就全懂了。 后缀自动机为什么难？后缀自动机是三个自动机里面最难的一个，难的地方不在与编码，在于他背后的数学推导， 想要完全理解后缀自动机，就必须深入理解什么叫自动机，这和AC自动机、回文自动机不同，因为AC自动机、回文自动机背后的数学推导过于简单。 自动机百度百科里面说的很清楚，也很抽象。自动机，是一个五元组，包含字符集，状态集合，初 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接http://codeforces.com/contest/1117/problem/D 题意你有两个数字：1和m， 你需要构造一个和为n的序列，问你能构造出多少种序列。答案对$10^9+7$取模。 范围$N\le10^{18}$ $M\le100$ 题解ans(n,m) = ans(n-1,m) + ans(n-m,m) 由于m一样，所以dp[n] = dp[n-1] + dp[n-m] 矩阵快速幂123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 ...