基本运算
一些常用的数学基本运算
快速幂&逆元
时间复杂度：$O(loga)$
//a^x
int q_pow(int a,int x){
int res=1;
while(x){
if(x&1)res=res*a%mod;
a=a*a%mod;
x>>=1;
}
return res%mod;
}快速幂同时可以用于求逆元，求 $a$ 在 $mod$ 下的逆元：$a’=$
q_pow(a,mod-2)
阶乘
阶乘预处理：
//fac[i]记录i的阶乘
ll fac[maxn]
void init(){
fac[0]=1;//0的阶乘为1
for(int i=1;i<maxn;++i){
fac[i]=fac[i-1]*i;
}
}模整数
const int mod=998244353;
struct Mint{
int v;
Mint():v(0){}
Mint(long long x){v=static_cast<int>((-mod<=x&&x<mod)?x:x%mod);if(v<0)v+=mod;}
friend Mint operator+(const Mint &a,const Mint &b){return (a.v+b.v)%mod;}
friend Mint operator-(const Mint &a,const Mint &b){return (a.v-b.v+mod)%mod;}
friend Mint operator*(const Mint &a,const Mint &b){
return static_cast<int>(1ll * a.v*b.v%mod);
}
friend Mint operator/(const Mint &a,const Mint &b){
return static_cast<int>(1ll*a.v*b.qpow(mod-2).v%mod);
}
friend ostream& operator<<(ostream &o,const Mint &t){o<<t.v;return o;}
Mint qpow(int x)const{
long long res=1,a=v;
while(x){
if(x&1)res=res*a%mod;
a=a*a%mod;
x>>=1;
}
return Mint(res);
}
};
using ll=Mint;位操作
检查2的幂次方
若一个数 $a$ 是 $2$ 的幂次方，则 $a&(a-1)=0$
数论-众数
摩尔投票算法
当一个元素出现超过 $n/2$ 时，可以用摩尔投票算法
时间为 $O(n)$ 空间为 $O(1)$
void find(){
int val = -1, cnt = 0;
while (n--) {
cin >> x;
if (!cnt) val = x;//没票换候选
(val == x) ? ++cnt : --cnt;//投票
}
cout << val;
}数论-平方数
平方和
平方和公式：
$$
S=1^2+2^2+…+n^2=\frac{n(n+1)(2n+1)}{6}
$$
立方和公式：
$$
S=1^3+2^3+…+n^3=(\frac{n(n+1)}{2})^2
$$
事实上，$k$ 次方和的计算结果可以用 $\frac{n^{k+1}}{k+1}$ 近似
平方数性质
定理1：
相邻两个平方数之间的差值构成公差为 $2$ 的等差数列，即
$$
i^2-(i-1)^2=2i-1
$$
定理2：
连续 $4$ 个平方数相加减可以得出固定值 $4$ ，即
$$
i^2-(i-1)^2=2i-1
$$
$$
(i-2)^2-(i-3)^2=2i-5
$$
两式相减得
$$
(i^2-(i-1)^2)-((i-2)^2-(i-3)^2)=4
$$
因此对于整数 $n$ ，可以通过有最多 $n+2$ 个平方数相加减来构成
不知听那位人士说过：遇到平方数先减一减再说…
3. 数论-素数
3.1 素数检测
3.1.1 Miller Rabin素数测试
快速判断一个数是否是素数
时间复杂度：$O(logn)$
//x为预判断的数
bool MillerRabin(ll x){
if(x<3||x%2==0)return x==2;
if(x%3==0)return x==3;
ll u=x-1,t=0;
while(u%2==0)u>>=1,++t;
for(int i=0;i<=8;++i){
ll a=rand()%(x-3)+2,v=q_pow(a,u,x);//保证a在2~x-2范围内,1,x-1,x能通过测试
if(v==1)continue;//之后操作都是1，直接通过
ll s;
for(s=0;s<t;++s){
if(v==x-1)break;
v=(lll)v*v%x;
}
if(s==t)return 0;
}
return 1;
}3.1.2 素数筛
3.2 质因数分解
3.2.1 朴素分解
可以结合线性筛，枚举 $[2,\sqrt{n}]$ 内的所有质数进行分解
时间复杂度：$O(\sqrt{n})$
优点：可以求出一个数所有的质因数
缺点：空间和时间都很高
vector<int> breakdown(int x) {
vector<int> ans;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) { //如果 i 能够整除 x，说明 i 为 x 的一个质因子。
while (x % i == 0) N /= i;
ans.emplace_back(i);
}
}
if (x != 1)ans.emplace_back(N);//说明再经过操作之后 N 留下了一个素数
return ans;
}3.2.1 Pollard rho 算法
可以求出给定数 $x$ 的某个非平凡因子
时间复杂度：$O(n^{\frac{1}{4}})$
//lll类型为__int128的别名，两个ll相乘时都要加上类型转换
//gcd()即为普通gcd，扩展版本的gcd(也可以通用
//q_pow()为快速幂，最后的参数是扩展的快速幂中的模数
//注意，快速幂中两个数相乘也要进行类型转换
typedef __int128 lll;
IN ll f(ll x,ll c,ll n){return ((lll)x*x+c)%n;}//伪随机序列
ll PR(ll x){//寻找x的一个非平凡因子
ll c=rand()%(x-1)+1;
ll t=0,s=0,val=1,goal,step;
for(goal=1;;goal<<=1,s=t,val=1){//goal每次倍增，
for(step=1;step<=goal;++step){
t=f(t,c,x);
val=(lll)val*abs(t-s)%x;
if(!val)return x;//val为0，分解失败，返回x重新分解
if(step%127==0){
ll d=gcd(val,x);
if(d>1)return d;
}
}
ll d=gcd(val,x);
if(d>1)return d;
}
}非平凡质因子：对于合数 $x$ ，它的非平凡质因子是不为 $1$ 或者 $x$ 本身的其他因子
若要对分解出的质因数进行筛选，则需要写控制函数，给出一种筛选最大质因数的写法
//ans记录最大质因子
ll ans=0;
void dfs(ll x){
if(x<=ans||x<2)return;//x比当前最大因子小，或者x为1，则都不能产生更大的因子
if(MillerRabin(x)){ans=max(ans,x);return;}//质因子，更新答案
ll p=x;
while(p>=x)p=PR(x);//产生一个小于x的因子
while(!(x%p))x/=p;
dfs(x),dfs(p);//检查因子和去掉这个因子的剩余部分
}3.3 哥德巴赫猜想
任意的偶数可以被两个质数之和表示
任意的奇数可以被三个质数之和表示
广义孪生素数猜想认为：任意偶数可以被两个素数之差表示，且这两个素数有无穷多组
数论-GCD
输入两个 $n$ 阶二进制数，有三种常见的GCD写法
普通GCD
利用辗转相除：$gcd(a,b)=gcd(b,a % b)$
时间复杂度：$O(n)$
int gcd(int a,int b){return !b?a:gcd(b,a%b);}二进制GCD
利用更相减损术+stein优化
更相减损术：$gcd(a,b)=gcd(a-b,b)$
stein优化：
- 若 $a,b$ 都为偶数，则 $gcd(a,b)=2gcd(a/2,b/2)$；
- 若 $a,b$ 中只有一个偶数，设 $a$ 为偶数，则$gcd(a,b)=gcd(a/2,b)$
时间复杂度：$O(logn)$
//—__builtin_ctz()计算一个数从末尾开始有几个二进制0，速度比按位枚举快
int gcd(int a,int b){
int az=__builtin_ctz(a),bz=__builtin_ctz(b);
int z=min(az,bz),dif;
b>>=bz;
while(a){
a>>=az;
dif=b-a;
az=__builtin_ctz(b-a);
if(dif>0)b=a,a=dif;
else a=-dif;
}
return b<<z;
}时间复杂度受到
__builtin_ctz()的影响，若改变int类型为long long类型，时间会翻倍
GCD性质
+A+B问题
对一个数 $S$ 不断进行 $+A,+B,-A,-B$ 四种操作，将会得到 $S+k\text{ gcd(A,B)}$
数论-组合数
组合数计算
组合数预处理
空间：$O(n^2)$
利用杨辉三角递推式计算：$C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$
int c[maxn][maxn];
void init(){
for(int i=0;i<=n;++i){
for(int j=0;j<=i;++j){
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1]);
}
}
}组合数直接计算
要配合阶乘预处理，空间 $O(n)$
利用组合数的定义式直接计算：$C_n^m=\frac{n!}{m!\cdot(n-m)!}$
需要阶乘预处理
ll C(ll n,ll m){return fac[n]/(fac[m]*fac[n-m]);}概率论
概率
概率DP
概率DP的范围就比较广泛了，主要总结一下题型
- 数据范围较小的时候可以DP，较大时概率为特定值
期望
连续型随机变量期望
连续型随机变量期望公式：$\int_{-\infty}^{\infty}xf(x)dx$
其中 $f(x)$ 为 $x$ 的分布，即取值为 $x$ 时，发生的概率
若发生事件的概率不变，但是值域发生变化，则只要改变积分范围
这种情况一般在多个目标对同一值域取值时发生，设初始值域为$[0,n]$，则
$E_i=\int_{0}^{n-\sum_{k=1}^{k=i-1} E_k}xf(x)dx$
分布模型
几何分布
离散概率分布的一种，描述独立实验中，第一次发生某事件所需要的实验次数。
若事件成功发生一次的概率为 $p$ ，则所需的试验次数期望为 $\frac{1}{p}$
这里的 “成功发生” 可以逆向思考
如某事件失败一次就会终止，问终止前期望可以成功几次
只要把 “成功发生” 的概率 $p$ 更换为失败的概率即可
博弈论
博弈论往往会有点摸不着头脑，可以先手玩几个试试。
NIM游戏
- 一堆石头，每个人每次能取走 $[1,k]$ 个石头，则石头数量为 $k+1$ 的倍数时，后手赢，否则先手赢。
除数博弈
- 有 $n$ 个石头，每次取走总数的约数，则 $n$ 为偶数先手赢(先手一直取 $1$)，否则后手赢(后手一直取 $1$)
筛法
线性筛
$O(n)$ 时间打出素数表
vector<int>pri;
bool m[maxn];
void init(){
m[1]=1;
for(int i=2;i<maxn;++i){
if(!m[i])pri.emplace_back(i);
for(auto t:pri){
if(i*t>=maxn)break;
m[i*t]=1;//质数的i倍一定是合数，标记
if(i%t==0)break;
//若i是某个质数的倍数，那i一定在遍历到这个质数时就被筛掉了
//所以i乘上后续的其他质数p，等价于k*t*p一定被t的其他倍数筛选，没必要再筛选下去了
}
}
}
