欧拉计划 解决一些数学问题的项目： : 。 以伦纳德·欧拉命名： : 2014 年 3 月 29 日：问题 1。3 或 5 的倍数之和。第 359659 个人解决此问题。 04/01/2014：问题 2。偶数斐波那契数的总和。 解决此问题的第 297816 人。 2014 年 4 月 30 日：问题 3。最大的质因数。 解决此问题的第 222097 人。 2014 年 5 月 24

0.如果不是秒切的话，解决问题的一般思路：

1.退而求其次：如果数据小、没有某个限制怎么办？（可以通过暴力分得到提示）

2.找到矛盾问题的根源，就是算法升级的关键，如果有了这个限制，怎么处理？

本篇博文记录一些机智操作，简洁方法，奇技淫巧。

支持：整形读入。包括负数

但是空间极其紧张，除非没时间改，否则不要用这个。

用num[0]计数，有多个数组的时候，不会弄混cnt名称

当数组中可能遇见负数的时候，可以考虑采用修正值fix，将取值的区域平移。

直接再加上n，平移到[0,n]就可以直接处理了。

二分一个中位数的值ans，大于ans的赋为1，小于-1（等于再说）

找区间内有无连续子段和大于0，判断ans+还是ans-

9.Hungary匈牙利算法每次memset的小优化（默认左部点出发dfs）

①一般情况下，我们是每次找到一个右部点，vis[y]=1，之后每次memset一下vis

②但是，有的时候，右部点很多，memset一下，nleft*nright 就挂了。

而如果左部点很少，可以尝试标记左部点的vis，

因为，我们之所以标记vis，是因为，不能在dfs(pre[y])时，从pre[y]里不断返回pre[y]自己（考虑代码模拟一下）。

如果标记左部点，那么，回到自己时，会因为已经vis，直接返回0

换句话说，①方案是不让你找到y，而②方案，是回到自己再打断。本质一样。

③我们也可以用一个栈sta[]，收集右部点vis的点，用弹栈并归零处理vis。

为什么复杂度在②条件下没问题？？

其实，最坏和②复杂度是一样的，一般情况下更优。

返回就返回了，打断搜索。如果dfs下去，那么必然要到了一个新的左部点。

所以，每vis一个，最多多访问一个左部点。所以，sta[]中元素的数量和左部点数量是一致的。

所以，最坏情况下，和②是一样的。

（  update:其实根本可以不用每次尝试清空什么vis！！！

我们可以采用时间戳的东西，vis[i]变成int数组，表示最后一次访问这个右部点的左部点的编号！

dfs序最小点和dfs序最大点取lca即可。

因为dfs总是先搜完一个子树，又因为两个点遍历时间相差最远。画图理解一下。

11.区间维护最小值，支持删除，插入

2.差的最小值呢？两个set，第二个set维护数值set相邻两个的差值。插入删除用前驱后继处理。

有的时候，出题人要卡你。一个哈希值可能出现的差错是：

本来不同的两个串，通过取模运算，就可能相同了。

所以，我们通过两个串，如果两个有一个哈希值不同，就认为串不同了。

注意，不可能出现相同的串哈希值不同的情况，因为算法一样，得到的哈希值一定相同。

13.曼哈顿距离转切比雪夫距离

这样，就可以把一个加法变成最值问题。

可以处理曼哈顿距离最小生成树。

用两个set一个维护没有加入当前点集中的点，横坐标，纵坐标。

用四个数维护当前点集最小x，最大x，最小y，最大y

每次从set找四个点和最小x，最大x，最小y，最大y找最小距离加进去。

因为，只要从x找一个max，y找一个max，再取max就可以。

14.变进制数存储状态，状压dp

就是，根据每个数的出现次数不同，每个数位置的进制都不同。

这样，可以达到压缩状态数到最小的结果。

即通过判断i，j所有公约数的u的和是否为1，判断i，j是否互质。

i，j互质的时候，公约数只有1，u(1)=1

i，j不互质的时候，公约数就是i，j最大公约数的约数。

那么，如果取两个以上的pi,u就是0，不影响答案。

所以，就是取p1、。。。pk一个或不取的方案数要考虑

根据组合数的性质，不论k是奇数还是偶数，答案都是0

17.曼哈顿距离和切比雪夫距离转化

18.gets()读入整行字符串，然后再 处理。

20.计算三角形面积。

21.二分图带权最大匹配

如果左部点只连接两个边，可以认为是两个右部点之间连接了一条边。

形成了一个无向图（可能不连通），相当于给边定向。

1.保留“a+b*根号”的形式：构造有序数对：(a,b)，即可定义乘法。

23.快速质因数分解：

如果要多次询问在1e7范围内的质因数分解，可以利用线性筛预处理每个数的最小质因子，然后不断除以mindiv，即可在低于logn时间下完成分解。

而且质因子已经自动排好序了。

24.十进制快速幂（专治高精快速幂）

和二进制快速幂原理一样。

每次x要左移一位，相当于一个快速幂$log_2 {10} $次。

但是，当y是一个高精度的时候，如果用十进制储存，每次/2是O(长度)的，会TLE。

然而十进制快速幂直接舍弃最后一位，可以O(1)进行移位。

（由于复杂度在低精度下是一样的，所以除了高精快速幂，并没有什么卵用）

对于O(1)判断si是sj的循环节：

证明方法类似kmp的循环节证明。

如果n是0，m是1的话，那么C(0,1)=0，那么就是0了。

28.所有取值的前k最值问题

考虑每个可能的决策点是否有贡献。

1.起初把每个点的最优解找出来，带着点的id，放进堆里面。

2.从堆里取出最优解。

3.把和这个id有关的次优解找出来，放进堆里。

适用于一些有固定可能存在的决策点。并且能够快速找到和这个点有关的第k优的值。

枚举每个决策点，计算决策点包含的物品的贡献——>枚举物品，计算对能产生影响的决策点的贡献。

后者，用于计数，就是分开考虑每个元素。对于最值决策，计算之后直接对决策点取最值。

工具——编译选项——编辑器——编辑时加入以下命令：-W -Wall

 31.对于一些序列两次取值的问题（两次取值位置不相交）

可以正着dp，f[i],前i个位置选择一个

再反着dp，g[i]i~n位置选择一个。

然后枚举分界点，即可。

一个数的所有非空前缀组成的数都是素数。

然而，雪球数有最大的数并不是无限的：

2.桌面新建文件。打开。

6.输入cd Desktop进入桌面界面（忘了文件名，输入ls Desktop 显示桌面的所有文件）

8.如果回车之后，没有其他信息（没有error），那么编译成功。

9.接下来输入./my.exe （注意之间没有空格）表示进入这个exe

然后类似windows下的cmd，直接输入数据即可。

 （按动↑可以寻找上面进行过的命令）

排序时，求向量旋转角的时候，用atan2(y,x)比较好

既可以保证精度，而且范围是在(-Pi,Pi]的。可以表示所有的旋转角。而且，如果atan2(t,0)的话(t>0)，会返回Pi/2,

适用于：FFT等需要四舍五入以及处理-0.0的情况。
（注意，负数的时候，强转int是向中取整，floor是向下取整，有所不同。看情况决定）

而且，FFT最后输出的时候，

用欧拉遍历序遍历树，然后RMQ记录深度。LCA就是之间深度最浅的，O(1)查询

38.堆优化dij的一个小剪枝

1.不必每次把所有的出边更新到的都加入到堆里

这样常数会小一些。多次dij，优化就明显了。

2.还可以用num记录已经确定的点的个数，如果num=0直接return

适当减少了常数（但是如果要多次dij的话，别忘了清空堆）

39.关于平均值的二分

上面有中位数的二分，平均值也可以二分

每个数减去平均值，如果区间和大于等于0，那么可以

一个有向图，S到T经过至少k条边的最短路，这个要T自己和自己连个自环，表示保留下来

缩减冗余状态：各种DP中用到

合并类似转移及状态：数组平移，维护分段函数，

修改之间忽视并不会变的：虚树、动态DP

42.异或下线性方程组的自由元个数：

然后高斯消元，如果某一个id找不到，那么一定是自由元了，计数器++

注意，每次找i和消除必须在全局位置，并且用一个vis标记表示是否还能动（因为有时候存在自由元X_i，但是第i行其实还能用）

最后削成的上三角矩阵，除了无解情况，剩下的一定有唯一解

（一般的线性方程组也是这样求，只不过xor下的自由元用的比较多）

43.一个通用技巧是：

f范围宽松好统计，g范围严格难统计但是和答案有直接关系，

这样，只要得到f和g的关系，就可以找到答案！

经常是可以得到f由g的表达式，然后斯特林反演或者二项式反演得到g的求法

数论函数的反演也可以这么做。

一些对于字典序大小，或者二进制下有大小比较限制的按位操作的题

枚举LCP可以有效体现比较大小的“实质”

一般外层枚举LCP，内层用DP处理方案。

46.一种生成函数还原序列的方法

有时候，两个生成函数卷积起来，要展开以后求x^k的系数，但是k很大。

①如果一个生成函数的次方的话，就是组合意义小球放盒子了，O(1)有公式，LUCAS求组合数

②否则考虑能不能把其中一个的生成函数变成有限项，使得项数在O(n)以内

47.给DAG转移重新定向

可以做到O(sqrt(m))的出边个数。支持暴力枚举

基于动态DP的思想，记录往轻儿子的贡献。重儿子现场计算。

便于打标记。便于写。（毕竟是静态树）

1.有标号图计数，F表示所有情况，G表示连通情况。则：G=Ln(F)

②把答案大的变小，仍然满足单调性，所以取最小值方案还是不变的。

4.求积分时候，处理分式分母。

前提是求一个分子分母都是连乘积的分式

可以考虑表示成：x*p^y的pair形式，最后上下把p的次数相减（类似扩展Lucas）

显然这样取模，mod的次数不会减少。

显然DINIC的瓶颈在于增广。

所以一些必然不会到达T的点就不用访问了。

所以从T开始搜分层图。

虽然一些点S不能到达，但是浪费的只是BFS的常数，反之浪费的就是增广时候的常数了。

O(p)预处理，O(1)任意底数，任意质数的快速幂

对于$G^{x}$可以直接预处理

 54.树上点集到点集的最大值

一个常用的套路：一个树上点集的直径，可以直接合并两个集合得到。四个端点C(4,2)计算即可。

猫的某个随机连通块直径题、安师大的某个O(n^4)预处理二分+前缀和查询、51nod1766

55.编号区间点集，信息可以合并？

一个常用套路：编号区间？线段树！线段树区间维护这个区间的信息即可

56.不能立刻决定球的颜色？

每个球的颜色个数固定，不能放一个球就染色

可以先认为是白色，然后某一个时刻钦定k个白色成为某一个颜色。只要知道之前有多少个白色就可以了。

如果遇到矩阵乘法套多项式，最后就求一个多项式的系数的话，可以考虑用IDFT的trick降低常数

具体是：直接把转移矩阵的x换成$w_N^i$，得到$Ans(w_N^i)$最后再插值。

一个乘法的常数，比卷积的常数小太多了。