算法学习心得与经验总结

其他的算法学习总结（持续更新）

莫比乌斯

技巧：https://www.cnblogs.com/linzhengmin/p/11060871.html
介绍：https://blog.csdn.net/tomandjake_/article/details/81083703
https://www.cnblogs.com/outerform/p/5921887.html


约数定理

约数定理：
设d(i,j)表示i*j的约数个数，则
d(i,j)=sum(x|i){sum(y|j)gcd(x,y)==1}
解释：枚举i的约数，j的约数，他们相乘就是新的约数。
但如果i=p^a,j=p^b,则在枚举i*j的因子时，会枚举a*b次，而我们要枚举a+b次。
这时只需要保证枚举的因子互质即可。


其他

自己总结：
0.一定化成与gcd有关的式子。
1.多用形式2
2.注意自己设的两个函数的意义是什么，看看能不能用什么式子（别的式子）表示一下。
3.多化成向下取整的除法形式，见到向下取整想分块
4.推式子时见到分数想换元，见到多个同样的乘积想换元。求向下整除，且被整除的数要从1到n
5.先化成和gcd有关的式子，一定要想办法用上分块：
6.对于乘法，一定要化成求和的形式。如果实在化不成，
看看能不能用当先以得出的式子的积性函数的性质。


一些遍历

前序遍历就是先遍历根节点,然后遍历左节点,最后是右节点;
中序遍历就是先遍历左节点,然后遍历中间的根节点,最后是右节点;
后序遍历就是先遍历左节点,然后遍历是右节点,最后是中间的根节点。


离散化

sort(b+1,b+totn+1);
totn=unique(b+1,b+totn+1)-b-1;
k[i]=lower_bound(b+1,b+totn+1,k[i])-b;


优先队列（堆）

不会写的话就用make_pair,这个是按照1,2，关键字排序的

struct node{
int u,w;
bool operator<(const node& rhs)const{
return w>rhs.w;
}
};


数论

二项式展开，欧拉定理，拆分因子，原根，相互整除是相等，gcd辗转相除判互质


DLX

图论的题别忘了可以单独光考虑边
交换：一个序列中，如果a,b可以换，a,c可以换，则可通过一定方式换b，c
线段树考察数不重复出现，可以在新遍历到的地方加上这个数，再把之前那个数去掉。


二项式反演反演原理：http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
恰好和至多至少



Min-Max熔池：https://blog.csdn.net/ez_2016gdgzoi471/article/details/81416333
考虑最大值最小值


这些和熔池原理的证明都考虑：单个元素对式子两边的贡献

期望概率可以考虑分组求：如果组与组之间没有联系，组数的期望，乘上每组的期望贡献