各种技巧摘抄

目录

二进制逆元质因数分解：冷知识

---

二进制

读取a的二进制第k位 a>>k&1 将a的第k位清零 a&=~(1<<k) 将a的第k位变成 a|=1<<k 将a的第k位取反 a^=1<<k

---

逆元

费马小定理求a在mod p意义下的inv：\(a^{p-2}=1/a((mod)p)\) 递推求inv :i在mod m下：\[t=m/i,k=m (mod) i,inv[i]=inv[k]*(m-t) (mod)m\]

---

质因数分解：

for(int i=2;i<=a;++i) { int s=0; while(a%i==0) { s++; a/=i; } cout<<i<<'^'<<s<<'\n'; }

---

冷知识

一、if(dis[s to x]+dis[x to t]==dis[s to t])则x在最短路上。

二、优化枚举的方法：1.二分，依赖于单调性2.倍增，原理为二进制拆分。

三、贪心算法常见证明方法： 1.微扰2.范围缩放3.决策包容性4.反证法5.数学归纳法

四、RMQ问题求解的一般方法： ST表，快速询问，难以插入，难以修改

笛卡尔树，简单插入，缓慢询问，难以修改

//ST表求解RMQ prework(): { for(int i=1;i<=n;++i) f[i][0]=a[i]; int t=log(n)/log(2)+1; for(int j=1;j<t;++j) for(int i=1;i<=n-(1<<j)+1;++i) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]; } query(l,r): { int k=log(r-l+1)/log(2); return max(f[l][k],f[r-(1<<k)+1][k]); }

分治法的等比數列求和

sum(p,c)=1+p+……+pow(p,c); ll get_sum(ll p, ll c) { if (!p) return 0; if (!c) return 1; if (c & 1) return (ksm(p, (c + 1) / 2) + 1) * get_sum(p, c / 2) % P; return ((ksm(p, c / 2) + 1) * get_sum(p, c / 2 - 1) + ksm(p, c)) % P; }

转载于:https://www.cnblogs.com/tztqwq/p/11137808.html

相关资源：JAVA上百实例源码以及开源项目