感觉我所有博客也就这篇比较全了QAQ
引入：Q1：前n个数中最多能取几个，使得没有一个数是另一个的倍数
答案：(n/2)上取整 p.s.取后n/2个就好了
Q2：在Q1条件下，和最小为多少
答案：从n/2向前枚举，对于每个数，倍增考虑后面选的数有多少个是它的倍数，如果只有一个，就用当前数替换后面的那个
正文：
零、快速幂&线性筛 【是个人都会系列】
快速幂
int Pow(int a,int b)
{
int ans=;
while(b>)
{
if(b%==) ans=(ans*a)%p;
b/=,a=(a*a)%p;
}
return ans%p;
}
线性筛（可以用来筛所有积性函数）
P.S.积性函数：f(a)*f(b)=f(a*b)当且仅当a,b互质
完全积性函数：f(a)*f(b)=f(a*b)
P.S.常见的积性函数：
①n的约数的k次幂的和 ∑ (d | n) (d^k)
②约数个数
③约数和
④欧拉函数
⑤莫比乌斯函数
P.S.因为算法是，质数&质数的整次幂暴力，其他的乘起来
所以必须有式子，且保证质数复杂度O(logn)以下，质数的整数次幂O(sqrt(n))以下才能保证线性
int n,cnt,pri[Mx];
bool jud[Mx]
void pre()
{
memset(jud,,sizeof(jud)); jud[]=;
for(int i=;i<=n;i++)
{
if(jud[i]) pri[++cnt]=i;
for(int j=;j<=cnt&&i*pri[j]<=n;j++)
{
jud[i*pri[j]]=;
if(i%pri[j]==) break;
}
}
}
一、欧几里得系列
gcd(a,b)=gcd(b%a,a)
exgcd:
已知Ax≡B (%C)
则Ax+By=C
int g=gcd(A,B,C)
设A'=A/g,B'=B/g,C'=C/g
则A'x+B'y=C'=1*(C')
由定理可知(B'%A')*x'+A'*y'=1 (x'表示x的逆元)
即(B'-A'(B'/A')下取整)*x'+A'*y'=1
所以A'*(y'-(B'/A')下取整*x')+B'*x'=1
所以x=y'-(B'/A')下取整*x',y=x'
迭代即可
最终x=C'(x0+B'*t),y=C'(y0-A'*t) ,t为任意值
真·欧几里得：
用于求某条直线下整数点的个数，自行看图吧QAQ
更相减损→辗转相除
二、逆元
Ax≡1(%p)
①ExGCD
②费马小定理：a^(p-1)≡1 (%p)，a'=a^(p-2)
③欧拉定理：a^φ(p)≡1 (%p)，a'=a^(φ(p)-1)
例：线性求1-n%p的逆元
方法一：威尔逊定理：(x+1)'≡(x+1)!'*x! (%p)
(x!)'≡(x+1)!'*(x+1) (%p)
则x'≡(x+1)!'*(x+1)*(x-1)! (%p)
先预处理阶乘，求出(n!)'，然后倒着推回来
void find(int n)
{
mul[]=;for(int i=;i<=n;i++) mul[i]=mul[i-]*i%p;
tmp[n]=pow(mul[n],phi[p]-)%p;
for(int i=n-;i>=;i--) tmp[i]=tmp[i+]*(i+)%p;
for(int i=;i<=n;i++) ans[i]=tmp[i]*mul[i-];
}
方法二：线性筛 (懒得写了TAT)
(a*b)'≡a'*b' (%p)
方法三：因为p=p%i- (p/i)下取整*i
所以i*(p/i)下取整≡-p%i (%p)
即i*(p/i)下取整*(-p%i)'≡1 (%p)
i'=(p/i)下取整*(-(p%i)')
三、BSGS
问题：A^x≡B (%C)
设x=i*m-j，m=⌈sqrt(C)⌉
则A^(i*m-j)≡B (%C)
即A^(i*m)≡B*A^j (%C)
枚举j (from 0~m)，将A^j*B存入hash表
枚举i (from 0~m)，从hash表中找到第一个满足上式的
找到时验证一下A^(i*m-j)是否为B，如果是，则x=i*m-j即为所求
若不是就继续走
ExBSGS
感觉没啥用...而且不是很懂啊......感觉博客写的莫名其妙的
C是质数会有一些性质比如说x%=p-1之类的...不过不是质数也能做
不管了扔上来再说吧QAQ
http://blog.csdn.net/reverie_mjp/article/details/51233630
四、中国剩余定理
问题：X≡a[i] (%b[i])
①：b[i]互质
设B=∏(i from 1~n) b[i]，b(i)=(B/b[i])对b[i]的逆
则X≡∑(i from 1~n) a[i]*(B/b[i])*b(i) (%∏(i from 1~n) b[i])
②：b[i]不互质
Exgcd
模线性方程组的合并：
X≡a1 (%b1)，即X=b1*y1+a2
X≡a2 (%b2)，即X=b2*y2+a2
所以对于b1*y1+b2*y2=a2-a1的任意解y1'
X≡y1'*b1+a1 (%lcm(b1,b2))
五、Miller-Rabin素数测试
这篇博客上说了一下Miller和Rabin怎么得到这个算法的：http://www.cnblogs.com/Norlan/p/5350243.html
简单介绍一下吧，就不证明了QAQ
定理：若p为素数且x<p，则x^2≡1 (%p)的解为x=1或x=p-1
若p为素数且x<p，则x^(p-1)≡1 (%p)
做法：提取p-1中的因子2，把p-1表示成d*2^r，如果p是一个素数，则a^d ≡1 (%p)，或存在某个i<r使得 a^(d*2^i) ≡n-1 (%p)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std; inline int mul(int a,int b,int p)
{
int c=; a%=p;
while(b)
{
if(b&) c=(c+a)%p;
b>>=;
a=(a+a)%p;
}
return c;
} inline int Pow(int a,int b,int p)
{
int c=; a%=p;
while(b)
{
if(b&) c=mul(c,a,p);
b>>=;
a=mul(a,a,p);
}
return c;
} bool Miller_Rabin(int n)
{
if(n==) return true;
if(n<||!(n&)) return false;
int m=n-,tot=;
int k = ;
while((m&)==) tot++,m>>=;
for(int i=;i<; i++)
{
int a=rand()%(n - )+;
int x=Pow(a,m,n),y=;
for(int j=;j<tot;j++)
{
y=mul(x,x,n);
if(y==&&x!=&&x!=n-) return false;
x=y;
}
if(y!=) return false;
}
return true;
} signed main()
{
int T; cin>>T;
while(T--)
{
int n; cin>>n;
if(Miller_Rabin(n)) puts("Yes");
else puts("No");
}
return ;
}
Pollard-rho
用于大数质因数分解
设p为要找的因子，一开始随机出一个数x1，不断构造xi=xi-12+c (c通常为1)，使p满足p|(xi-x2)&&(x1-x2)|n
可以证明p=gcd(n,x1-x2)，且若p!=1则表明找到了一个因子，直到xi出现循环
如图：
六、知识点补充
①：整除
②：取模
(a*p)%(b*p)=(a%b)*p
(a%(b*c))%c=a%c
a%b=a-b*(a/b)下取整
③：(x+a)^n=∑(k from 0~n) C(n,k)*(x^k)*(a^(n-k))
1/(1-x)=∑(k from 0~inf) x^k
1/((1-x)^2)=∑(k from 0~inf) (k+1)*(x^k)
1/(1-x^n)=∑(k from 0~inf) x^(k*n)
④：五边形数：f[n]=n*(3n-1)/2
广义五边形数：f[n][0]=n*(3n-1)/2，f[n][1]=n*(3n+1)/2
分割函数p(n)（对整数n进行拆分）：p(n)=p(n-f[1][0])+p(n-f[1][1])-p(n-f[2][0])-......
⑤ 1)Q：n个人m个凳子排成一列，任意两个人的距离不小于k，求方案数
A：考虑前n-1个人，并删去最后k张椅子，则方案数为C(m-(n-1)*k,n)
2)Q：n个人m个凳子形成一个环，任意两个人的距离不小于k，循环翻转不同构，求方案数
A：破环成链，取长度为k+1的椅子，考虑放不放人
如果放一个人，问题转化为m-2*k-1的链上放n-1个人，若未放人，则为m-k-1的链上放n个人的问题
ans=(k+1)*C(m-2*k-1-(n-2)*k,n-1)+C(m-k-1-(n-1)*k,n)， p.s. n=1时ans=m
⑥：问题：已知b[i]=∑(j from1~n) a[i]&a[j]，
c[i]=∑(j from 1~n) a[i]|a[j]，
给出b数组，c数组，构造a数组或输出无解
结论：(a|b)﹣(a&b)=a xor b
(a|b)＋(a&b)=a+b
所以b[i]+c[i]=n*a[i]+suma，即可构造a数组
七、Lucas定理
C(n,k)=∏(i from 0~k) C(a[i],b[i]) (%p(p为素数))，a[i],b[i]表示p进制下n,k每一位的数字
即C(n,k)=C(n%p,k%p)*C(n/p,k/p)，递归解决
例：bzoj1902：http://www.cnblogs.com/xiaoxubi/p/6557598.html
ExLucas定理
orz....http://m.blog.csdn.net/article/details?id=52176653
当p不是素数时使用
将p拆成∏pi^qi，然后用crt合并即可
考虑在%pi^qi下的结果
因为C(n,m)=n!/(m!*(n-m)!)，这里我们考虑对n!进行变换，以n=11,pi=2,qi=2为例
11!=1*2*3*4*5*6*7*8*9*10*11
=1*3*5*7*9*11*(2*4*6*8*10)
=(1*3*5*7*9*11)*2*(5!)
可以发现阶乘被分为3个部分
第一部分以pi^qi为周期同余（(1*3*5)≡(7*9*11)%4），最后一部分不超过p，直接计算即可
第二部分为pi^k，这里统计一下n!、m!、(n-m)!中pi倍数的数得个数，直接计算即可
第三部分为⌊n/p⌋!，递归计算即可
八、原根和指标
缩系：
定义：%p意义下与p互质的元素的集合，大小为φ(p)，任意两个元素的乘积也在缩系中
阶：
定义：满足x^k≡1 (%p)的最小的k，记为ord(x)
P.S. ord(x) | φ(p)
原根：
定义：缩系中存在元素g，使g^i (i from 1 to φ(p)) 两两不同，则g为%p意义下的原根
性质：①∀i,j，i!=j&&i,j<=p-1，g^i!≡g^j (%P)
②g^i≡1 (%P) 当且仅当i=P-1时成立
③ord(g)=φ(P)
④原根有φ(φ(p))个 （如果存在原根）
⑤%p有原根的充要条件是p=质数^k 或 2*质数^k
求法：从2开始暴力枚举g，利用性质2暴力判断即可
指标（离散对数）：
定义：元素x≡g^i (%p)的指标ind(x)≡i (%φ(p))
P.S. ord(m) = φ(m)/gcd(φ(m),ind(x))
十、狄利克雷卷积
定义：函数f(x)和g(x)的狄利克雷卷积（记为 (f*g) (x)）
(f*g) (n)=∑ (d | n) f(d)*g(n/d)
性质：交换律：f*g=g*f
结合律：(f*g)*h=f*(g*h)
分配律：f*(g+h)=f*g+f*h
单位元：f*e=f
若f,g为积性函数，则f*g为积性函数
杜教筛
定义：用狄利克雷卷积构造来快速计算积性函数f(x)的前缀和S(x)
复杂度：O(n^(3/4))，若用线性筛预处理前n^(2/3)则可达到O(n^(2/3))
令F(n)=∑(i from 1 to n) f(i)，g(n)=∑(d|n) f(d)，G(n)=∑(i from 1 to n) g(i)
P.S.要求G(n)可以O(1)求得
则G(n)=∑(j from 1 to n) ⌊n/j⌋*f(j)
=∑(j from 1 to n) F(⌊n/j⌋)
所以F(n)=G(n)-∑(j from 2 to n) F(⌊n/j⌋)
例：http://www.lydsy.com/JudgeOnline/problem.php?id=3944
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
const int Mx=;
map <int,ll> Phi,Miu;
map <int,ll> ::iterator it;
int n,cnt,pri[Mx/+],Div[Mx+];
ll phi[Mx+],miu[Mx+];
void pre()
{
phi[]=miu[]=;
for(int i=;i<=Mx;i++)
{
if(!Div[i]) pri[++cnt]=i,miu[i]=-,phi[i]=i-;
for(int j=,tmp;pri[j]*i<=Mx;j++)
{
tmp=pri[j]*i,Div[tmp]=pri[j];
if(i%pri[j]==)
{
miu[tmp]=,phi[tmp]=phi[i]*pri[j];
break;
}
miu[tmp]=miu[i]*-,phi[tmp]=phi[i]*(pri[j]-);
}
}
for(int i=;i<=Mx;i++) miu[i]+=miu[i-],phi[i]+=phi[i-];
}
ll get_phi(int x)
{
if(x<=Mx-) return phi[x];
if((it=Phi.find(x))!=Phi.end()) return it->second;
ll ans=x*(x+1ll)/;
for(ll i=,nxt;i<=x;i=nxt+)
nxt=x/(x/i),ans-=get_phi(x/i)*(nxt-(i-));
return Phi[x]=ans;
}
ll get_miu(int x)
{
if(x<=Mx-) return miu[x];
if((it=Miu.find(x))!=Miu.end()) return it->second;
ll ans=;
for(ll i=,nxt;i<=x;i=nxt+)
nxt=x/(x/i),ans-=get_miu(x/i)*(nxt-(i-));
return Miu[x]=ans;
}
int main()
{
pre();
int T; scanf("%d",&T);
while(T--)
scanf("%d",&n),
printf("%lld %lld\n",get_phi(n),get_miu(n));
return ;
}
十一、莫比乌斯反演
μ函数：μ(n)=1，n=1
=0，n=0或将n质因数拆分后有平方项
=(-1)^r，r表示将n质因数拆分后的项数
定理：① f(n)=∑g(d)=∑g(n/d),d|n
⇔ g(n)=∑μ(d)*f(n/d)=∑μ(n/d)*f(d),d|n
② ⌊ x / ab ⌋ = ⌊ ⌊x/a⌋ / b ⌋ = ⌊ ⌊x/b⌋ / a ⌋，上取整也一样
③ 对于函数f(),g(),t()，若t()为完全积性函数，则
f(n)=∑ (k from 1 to n) t(k)*g(⌊n/k⌋)
⇔ g(n)=∑ (k from 1 to n) μ(k)*t(k)*f(⌊n/k⌋)
性质：①μ为积性函数，即μ(a*b)=μ(a)*μ(b)
②若f为积性函数，则g为积性函数
μ的应用：①∑μ(d)=0,d能整除n且n!=1，(n=1时ans=1)
②gcd(a,b)=1等价于∑μ(d)=1,d%gcd(a,b)==0||(d%i==0&&d%j==0)
求法：线性筛
例：
bzoj4816：http://blog.csdn.net/qq_31776811/article/details/70148197
n*m点阵可见点数
二项式反演：①f(n)=∑C(n,i)*g(i),i<=n
g(n)=∑((-1)^(n-i))*C(n,i)*f(i),i<=n
②应用：Q1 求n个元素恰好m个错位的方案数D(m)
首先因为全排列可知∑C(n,k)*D(k)=n!,k<=n
反演可得D(m)=∑((-1)^(m-k))*C(m,k)*k!,k<=m
=m!*∑((-1)^k)*(1/k!),k<=m
Q2
Q3
十二、线性代数
①行列式：例，对于矩阵A{1 3 2}，求其行列式
{5 1 6}
{3 0 7}
步骤：1)写出其行数的全排列a[i][j] 123 132 213 231 312 321
2)求出每个排列的逆序对数num[i] 0 1 1 2 2 3
3)将第j行第a[i][j]个数相乘记为sum[i] 7 0 105 54 0 6
4)A的行列式det(A)=∑sum[i]*((-1)^num[i])=7*(-1)^0+0*(-1)^1+...+6*(-1)^3=-50
算法：1)将矩阵消成对角线
2)统计交换了cnt次行
3)det(A)=对角线乘积*((-1)^cnt)
P.S. det(A*B)=det(A)*det(B)
②基尔霍夫矩阵：给定n个点，m条边的无向图，求生成树计数
例：对于下图
邻接矩阵存图：map[i][j]表示i与j之间边数的相反数
map[i][i]表示点i的度数
求行列式，即为答案
即将矩阵化为三角形矩阵后求对角线乘积即可
P.S.将矩阵的某一行同时除以某个数，行列式的值不变。
矩阵的某两行相交换，行列式的值取相反数。
③矩阵乘法：1)有向图从i到j走k步的方案数：
map[i][j]为i-j的边数
ans={0,1,1}^(k-1)的右下角
{0,0,1}
{0,1,0}
复杂度：O(n^3)
2)有向图从i到j走k~l步的方案数：
加一行一列
ans={0,1,1,0}^(l-1)的右下角-map^(k-1)的右下角
{0,0,1,0}
{0,1,0,0}
{0,0,0,1}
3)无向图从i到j走k步的方案数：同①，只用算倒三角
4)循环矩阵，如{1,2,3}，只算第一行第一列，其余递推，O(n^2)
{3,1,2}
{2,3,1}
④高斯消元&线性基：
每次选取位数最高的行，假设最高位在第k位，用该行和所有最高位在第k位的行异或起来即可
例：bzoj3105：http://www.cnblogs.com/xiaoxubi/p/6543458.html
bzoj2115：http://www.cnblogs.com/xiaoxubi/p/6543252.html
bzoj2844：http://www.cnblogs.com/xiaoxubi/p/6541257.html
void gauss()
{
for(int i=;i<=n;i++) sum+=a[i];
for(int i=;i<=n;i++)
{
int tmp=a[i];
for(int j=;j>=;j--)
if(a[i]&Pow[j])
{
if(!b[j]) { b[j]=i; break; }
else a[i]^=a[b[j]];
}
if(a[i]) ans+=tmp;
}
}
⑤矩阵的秩&*元：
*元：高斯之后一行全为0的行数
秩：行数-*元
⑥矩阵快速幂：
构造转移矩阵+用快速幂实现矩阵乘法即可
难点在构造转移矩阵QAQ
例：斐波那契数列
十三、置换群
①概念：1)群：具有某些特殊性质的集合
1 封闭性：∀f,g∈G,f*g=h,则h∈G;
2 结合律：∀f,g,h∈G,(f*g)*h=f*(g*h);
3 有单位元：∃e∈G,∀f∈G,f?e＝e?f＝f;
4 有逆元素：∀f∈G,∃f^-1∈G,使f*(f^-1)=(f^-1)*f=e;
2)置换群：一些置换的集合，满足群的性质
②Burnside引理
L=(1/G)*∑c(a[i]),(i from 1 to G)
L表示循环同构的染色方案数
G表示置换群中的操作个数，a[i]表示每一个操作
c(a[i])表示在a[i]操作下的不动点数（转后与原来一样）
如图，不动(360度)：a1=(1)(2)…(16)
逆时针转90度 ：a2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)
顺时针转90度 ：a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
转180度：a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16)
L=1/4*(16+2+2+4)=6
③Polya定理
用于解决n元环m染色问题
L=(1/G)*∑f(c(a[i])),(i from 1 to G)=(1/G)*∑m^(c(a[i])),(i from 1 to G)
L,G,c,ai与Burnside引理相同，m为染色数，f()为自己定义的一个函数
1 循环同构：L=(1/m)*∑n^(gcd(i,m)),(i from 1 to m)
2 循环、对称同构：
n是奇数：L=(1/2n)*(∑n^(gcd(i,m),(i from 1 to m))+n*m^(┌(n/2)┐)
n是偶数：L=(1/2n)*(∑n^(gcd(i,m),(i from 1 to m))+((n/2)*(m^(n/2+1)+m^(n/2))
十四、泰勒展开
公式：
解释：
感性的理解一下，对于一个多项式，求导得到的是每一项的系数，这样做显然是正确的
而对于非多项式可以用多项式拟合（逃~
多项式版本（牛顿二项式定理）：
P.S.感觉我这写的好乱啊QAQ
常见函数的泰勒展开式（非多项式）：
e^x = 1+x+x^2/2!+x^3/3!+……+x^n/n!+……
ln(1+x)=x-x^2/2+x^3/3-……+(-1)^(k-1)*(x^k)/k(|x|<1)
sin x = x-x^3/3!+x^5/5!-……+(-1)^(k-1)*(x^(2k-1))/(2k-1)!+……。(-∞<x<∞)
cos x = 1-x^2/2!+x^4/4!-……+(-1)k*(x^(2k))/(2k)!+…… (-∞<x<∞)
arcsin x = x+(1/2)*x^3/3+(3/8)*x^5/5 + ……(2k)!/((4^k)*((k!)^2))*x^(2k+1)/(2k+1)(|x|<1)
arccos x = π/2 - ( x + (1/2)*x^3/3 + (3/8)*x^5/5 + …… ) (|x|<1)
arctan x = x - x^3/3 + x^5/5 -……(x≤1)
sinh x = x+x^3/3!+x^5/5!+……+(-1)^(k-1)*(x^2k-1)/(2k-1)!+…… (-∞<x<∞)
cosh x = 1+x^2/2!+x^4/4!+……+(-1)k*(x^2k)/(2k)!+……(-∞<x<∞)
arcsinh x = x - 1/2*x^3/3 + 1*3/(2*4)*x^5/5 - …… (|x|<1)
arctanh x = x + x^3/3 + x^5/5 + ……(|x|<1)
十五、
P.S.感觉这些东西百度百科就讲的挺清楚的QAQ
P.S.并不会母函数什么的......我还是太弱了QAQ
母函数的坑终于填上了，累死了QAQ
斐波那契数列
通项公式：
前缀和：∑f(k),(k from 1 to n)=f(n+2)-f(2)
奇数项和：∑f(2*k-1),(k from 1 to n)=f(2n)
平方和：∑f(k)^2,(k from 1 to n)=f(n)*f(n+1)
相邻项乘积和：∑f(k)*f(k+1),(k from 1 to n)=(1/2)*(f(n+2)^2-(f(n)*f(n+1))-1)
性质1：f(n)^2=f(n-1)*f(n+1)+(-1^n)
性质2：f(m+n)^2-f(m-n)^2=f(2m)*f(2n)
性质3：(f(n-1)*f(n+2))-(f(n)*f(n+1))=(-1)^n
性质4：f(n)在%p意义下纯循环
若p=10^n，则循环节长度为6*p
应用1：已知a^2=a+1,a^3=a^2+a.....,求a^n=?
解：a^n=f(n)*a+f(n-1)
应用2：生成勾股数
卡特兰数
递推式：h(0)=1,h(1)=1,h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
h(n)=h(n-1)*(4*n-2)/(n+1)
h(n)=C(2n,n)/(n+1)
h(n)=c(2n,n)-c(2n,n-1)
应用：括号化（对满足结合律的式子添加括号）：h(n)
n个数的出栈序列种类：h(n)
凸多边形的三角形划分方案数：h(n-2)
n个节点的二叉搜索树种类：h(n)
在n位的2进制中，有m个0，其余为1的卡特兰数为C(n,m)-C(n,m-1)
斯特林数
第一类：无符号：s(0,0)=1,s(i,0)=0,s(n,m)=s(n-1,m-1)+(n-1)*s(n-1,m)
∑(k from 0~n) s(n,k)=n!
有符号：s'(n,m)=(-1)^(n+m)*s(n,m)
∑(k from 0~n) s'(n,k)=0^n
应用：升阶&降阶函数的系数（这个地方本人不是太明白呢QAQ，所以各位dalao请自行看百度百科）
将n个不同元素构成m个圆排列的方案数
解锁仓库问题
第二类：递推式：s(0,0)=1,s(n,m)=s(n-1,m-1)+m*s(n-1,m)
应用：m个盒子放n个不同的球，盒子（有标号or无标号or允许空）
不同盒子相同球：插隔板，C(n-1,m)
相同盒子相同球：整数划分，dp，f(n,m)=f(n-m,m)+f(n,m-1)
f(n,m)表示将n划分为不超过m的若干个整数
通项公式：
通项公式可用容斥原理推导
P.S.∑s(n,k)=B(n)，即贝尔数
贝尔数
递推式：B(0)=1,B(n+1)=∑(k from 0 to n) C(n,k)*B(k)
B(p+n)=B(n)+B(n+1) (%p),p为质数
通项公式：
，Dobinski公式：期望值为1的泊松分布的n次矩
，即B(n)为第二类斯特林数的总和
应用：将n个元素划分的方案数
调和级数
通项公式：H(n)=∑(k from 1 to n) 1/k
前缀和：∑(k from 1 to n) H(k)=(n+1)*H(n)-n
P.S.调和级数是发散的
伯努利数
定义：
性质：①∑(k from 0 to n) C(n,k)*B(k) =0
可以用递推求各项，递推式：
可以围观dalao博客：http://blog.csdn.net/acdreamers/article/details/38929067
也可以O(nlogn)递推，用指数母函数展开然后balabala.....
就是将定义中的e^x泰勒展开一下然后，搞成了这么个东西
然后你把分母多项式在%pow(x,n+1)意义下求个逆，%pow(x,n+1)就是将Bn以上的项都消掉
然后对于x^i其系数就是Bi啦！（终于搞定了QAQ）
②B(0)=1,B(1)=-1/2
B(k)=0，k为奇数
用途：根据公式
O(k^2)预处理每一部分，可以在每个case以O(k)求出∑ i^k
若k特别大也可以O(klogk)预处理，每个case O(klogk)
默慈金数
http://blog.csdn.net/acdreamers/article/details/41213667
递推式：
应用：①在圆上的n个点间画出不相交的弦的方案数
②在网格图中只允许向右、上、下走，从(0,0)走到(n,0)的方案数
那罗延数
http://blog.csdn.net/whai362/article/details/42674431
通项公式：N(n,k) = 1/n * C(n,k) * C(n,k-1)，（C为组合数）
求和：∑(k from 0 to n) N(n,k)=Catalan(n)
应用：在由n对"("和")"组成的字符串中，共有k对"("与")"相邻的字符串个数
十六、康托展开：
公式：X()=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!
例：对于数组s=[A,B,C,D]及其排列s1=[D,B,A,C]，将s1映射成X。
X(s1) = a4*3! + a3*2! + a2*1! + a1*0!
a4表示"D" 这个元素在子数组[D,B,A,C]中是第几大的元素(下标从0开始)，a4=3
a3表示"B" 这个元素在子数组[B,A,C]中是第几大的元素，a3=1
a2表示"A" 这个元素在子数组[A,C]中是第几大的元素，a2 = 0
a1表示"C" 这个元素在子数组[C]中是第几大的元素，a1=0
即X(s1) = 3*3! + 1*2! + 0*1! + 0*0! = 20
康托逆展开：生成全排列&第m个排列
//copy from zhongkeli's blog
//第m个排列
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
class cantor{
public:
int n;//字符串的长度
string s;
int pos;//字符串在全排列中的字典位置，从0开始
vector<int>num;//所有的字符
cantor(string s):s(s){n=s.size();}
cantor(int n,int pos):n(n),pos(pos){
int i;
for(i=;i<n;i++)
num.push_back(i);
}
int fac(int);
void encode();
void decode(); };
int cantor::fac(int num){
if(num==) return ;
else return num*fac(num-);
}
void cantor::encode(){
int i,j,count;
vector<int>vec(n);
for(i=;i<n;i++){
count=;
for(j=i;j<n;j++)
if(s[i]>s[j]) count++;
vec[n-i-]=count;
}
pos=;
for(i=;i<s.size();i++)
pos+=vec[i]*fac(i);
}
void cantor::decode(){
int i;
div_t divresult;
for(i=n-;i>=;i--){
divresult=div(pos,fac(i));求余数与除数
s.push_back(num[divresult.quot]+'');
num.erase(num.begin()+divresult.quot);
pos=divresult.rem;
}
}
int main(){
cantor test(,);
test.decode();
cout<<test.s<<endl;
}
十七、母函数（生成函数）
填坑，学了一下午，累死了QAQ
matrix67的博客喵啊：http://www.matrix67.com/blog/archives/120
生成函数
用于解决多重集的组合问题，如题：http://acm.hdu.edu.cn/showproblem.php?pid=2082
构造数列{a0...an}的母函数G(x)， G(x)=∑ (i from 0 to n) (ai*(x^i))
题意：n种物品，数量分别为k1...kn（可为无穷），价值p1…pn，求价值和为m的物品组合方法数
构造母函数G(x)=∏(i<=n) ∑(j<=ki) x^(j*pi)
=∑ ak*x^k
答案即为am
指数型生成函数
用于解决多重集的排列问题，如题：http://acm.hdu.edu.cn/showproblem.php?pid=1521
构造数列{a0...an}的指数型母函数G(x)，G(x)=∑ (i from 0 to n) (ai*(x^i)/(i!+(i==0))
题意：有n种物品，数量分别为k1..kn，求从中选出m个物品的排列方案数
P.S.选n个物品（全排列）：n!/∑ ki!
构造指数型母函数G(x)=∏(i<=n) ∑(j<=ki) ((x^j)/(j!+(j==0))
答案即为am
P.S.限制条件可以直接在那个∑里把对应的项删掉就行啦QwQ
十八、快速傅里叶变换FFT&NTT
感觉这篇博客讲的挺清楚的：https://www.zybuluo.com/397915842/note/37965
还有一个：http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-15
FFT是用复数来处理多项式乘法的，NTT是在模意义下做多项式乘法的，NTT就是将FFT中的复数i替换为p的原根
所以这里我们只陈述FFT的工作原理
考虑要想确定一个n阶多项式∑ai*(x^i)，需要n+1个点
设多项式A,B，将其分别拆成2n+1个点(ai.x,ai.y),(bi.x,bi.y)，则其乘积为(ai.x*bi.x,ai.y*bi.y)所对应的多项式
而FFT是用于加速函数式和点值式的相互转化的，这里仅讨论函数式→点值式的转化
考虑将x赋值为e^0 ~ e^(n-1)，e=cos(π*i/n)+sin(π*i/n)*sqrt(-1)，可使向量构成一个满足e^n=e^0的环，
即x^k每n位一循环即可快速解决此问题
对于原式∑ai*(x^i)，考虑分治，将其按i的奇偶分成两块，即∑ai*xi(i为奇数)+∑aj*xj(j为偶数)
考虑解决左半边，将x提出后可化为x*∑a(2i+1)*x^(2i)，这里我们发现虽然i减半了，但是x的次数并没有变
考虑将x赋值为e^k，则原式可化为x*∑a(2i+1)*e^(2ik)，即x*∑a(2i+1)*(e^2k)^i
当k<n/2时原式可看做x*∑a(2i+1)*x^i，而当k>n/2时设t=k-n/2，则e^2k=e^2t，令k=t即可回到k<n/2的问题
于是我们便可以递归解决该问题了，P.S.为方便实现，我们可以将n补成2的整数次幂
对于点值式→函数式的变换，再做一遍FFT即可，不过e的纵坐标要取负，ai’=n*ai
P.S.蝴蝶变换可以将代码变成非递归的，优化常数：http://www.cnblogs.com/zpfbuaa/p/5081155.html
例：bzoj2179：FFT
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<complex>
#define pi 3.141592653589
using namespace std;
const int Mx=;
typedef complex <double> C;
int n,m,l,r[Mx],c[Mx];
char s[Mx],t[Mx];
C A[Mx],B[Mx];
void fft(C *A,int tag)
{
for(int i=;i<n;i++) if(r[i]>i) swap(A[i],A[r[i]]);
for(int i=;i<n;i<<=)
{
C e(cos(pi/i),tag*sin(pi/i));
for(int j=;j<n;j+=i<<)
{
C ei=;
for(int k=;k<i;k++,ei*=e)
{
C x=A[j+k],y=ei*A[j+k+i];
A[j+k]=x+y,A[j+k+i]=x-y;
}
}
}
}
int main()
{
scanf("%d%s%s",&m,s,t);
for(int i=;i<m;i++) A[i]=s[m-i-]-'',B[i]=t[m-i-]-'';
for(n=,m<<=;n<m;n<<=) l++;
for(int i=;i<n;i++) r[i]=(r[i>>]>>)|((i&)<<(l-));//蝴蝶
fft(A,),fft(B,);
for(int i=;i<n;i++) A[i]*=B[i]; fft(A,-);
for(int i=;i<n;i++) A[i]/=n;
for(int i=;i<m;i++) c[i]=(int) (A[i].real()+0.1);
for(int i=;i<m;i++)
if(c[i]>=) c[i+]+=c[i]/,c[i]%=;
else if(!c[i]&&i==m-) m--;
for(int i=m-;i>=;i--) printf("%d",c[i]);
return ;
}
uoj 34：NTT
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int Mx=;
const int p=;
const int g=;
int n,m,l,top,rev[Mx];
int A[Mx],B[Mx],C[Mx];
inline int Pow(int a,int b)
{
int c=;
while(b)
{
if(b&) c=(c*a)%p;
a=(a*a)%p;
b/=;
}
return c;
}
void NTT(int *A,int tag)
{
for(int i=;i<n;i++) if(rev[i]>i) swap(A[i],A[rev[i]]);
for(int i=;i<n;i<<=)
{
int e=Pow(g,(p-)/(i<<));
for(int j=;j<n;j+=i<<)
{
int ei=;
for(int k=;k<i;k++,ei=(e*ei)%p)
{
int x=A[j+k],y=(ei*A[j+k+i])%p;
A[j+k]=(x+y)%p,A[j+k+i]=(x-y+p)%p;
}
}
}
if(tag==-) //翻回来要除n
{
reverse(A+,A+n);
for(int i=,ni=Pow(n,p-);i<n;i++) A[i]=(A[i]*ni)%p;
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
for (int i=;i<=n;i++) scanf("%lld",&A[i]);
for (int i=;i<=m;i++) scanf("%lld",&B[i]);
m=n+m; for(n=;n<m;n<<=) l++;
for(int i=;i<n;i++) rev[i]=(rev[i>>]>>)|((i&)<<(l-));//蝴蝶
NTT(A,);NTT(B,);
for(int i=;i<n;i++) A[i]=(A[i]*B[i])%p;
NTT(A,-);
for(int i=;i<=m;i++) printf("%lld ",A[i]);
return ;
}
十九、多项式求逆&除法&取模
求逆：
orz Miskcoo：http://blog.miskcoo.com/2015/05/polynomial-inverse#i-5
设A[]为给定多项式，B[]=A[]^-1 (%x^n) P.S.也就是只留x^0...x^(n-1)的项
假设已经求出B[]在%x^⌈n/2⌉意义下的各项系数记为B'[]，即A[x]*B'[x]≡1 (%x^⌈n/2⌉)
又因为在%x^n下成立的式子在%x^⌈n/2⌉意义下也成立，则有以下式子
①A[x]*B[x]≡1 (%x^⌈n/2⌉)
②A[x]*B'[x]≡1 (%x^⌈n/2⌉)
①-②可得：B[x]-B'[x]≡0 (%x^⌈n/2⌉)
两边平方：B[x]^2+B'[x]^2-2*B[x]*B'[x]≡0 (%x^n)
关于为什么是%x^n的话dalao的博客里有证明，我截个图贴上来QAQ
然后两边*A[]，移项可得：B[x]=2*B'[x]-A[x]*B'[x]*B'[x]
利用倍增+FFT即可O(nlogn)计算，边界条件：B[0]=A[0]'
代码抄Yousiki的：http://yousiki.net/index.php/archives/39/
void inv(int *a, int *b, int len)
{
if (len == )
b[] = pow(a[], mod - );
else
{
inv(a, b, len >> ); static int t[mxn]; memcpy(t, a, len * siz);
memset(t + len, , len * siz); ntt(t, len << , +);
ntt(b, len << , +); for (int i = ; i < (len << ); ++i)
b[i] = mul(b[i], ( - mul(t[i], b[i]) + mod)); ntt(b, len << , -); memset(b + len, , len * siz);
}
}
除法&取模：
http://blog.miskcoo.com/2015/05/polynomial-division
设A[]/B[]=D[],A[]%B[]=R[]，则A(x)=B(x)*D(x)+R(x)，求D(x)
考虑将x变为1/x，再将多项式*xn，则相当于将多项式系数反转，记为AR(x)
如：
考虑对原多项式也做类似的处理：将x变为1/x并在等式左右同乘x^n
P.S.我们可以把R看成m阶多项式
即：
我们发现，D(x)的系数不会大于n-m，又因为RR的系数为n-m+1，那么RR即可消掉
即：
对BR求个逆然后一路推回去就可以得到D[]和R[]了
二十、牛顿迭代法
牛顿迭代法：
Matrix67：http://www.matrix67.com/blog/archives/361
用于解决寻找平方根的问题
随机一个点，每次找切线和x轴的交点，以这个x值的(x,f(x))为新的点继续操作，直到找到0点
牛顿迭代法在多项式运算的应用：
Picks：http://picks.logdown.com/posts/209226-newtons-method-of-polynomial
Miskcoo：http://blog.miskcoo.com/2015/06/polynomial-with-newton-method
感觉Miskcoo说的挺清楚的了就不想再总结了，生成函数不懂的话看前面的条目就行
感觉又挖了个二次剩余的坑.....不过我是不想填了
想看的自己戳这里吧：http://blog.miskcoo.com/2014/08/quadratic-residue
二十一、计算几何
凸包：
贴几篇博客吧，感觉第一个讲的不错，第二、三个比较全
P.S.第一篇分了三章我只贴了一张，需要自己去博主列表翻QAQ
http://www.cnblogs.com/Booble/archive/2011/02/28/1967179.html#3229390
http://blog.csdn.net/hanchengxi/article/details/8639476
定义：对于一个点集S，找出其中最小的一个子集S'，对于S'的两个相邻顶点的边，所有点都在边的同一侧
如：
做法：
Graham扫描算法
先找出左下角的点（肯定在凸包上），考虑如何找下一个点
利用向量叉积的正负来判断，用一个栈来维护
先按极坐标排序，将第一个点入栈然后向下一个点连边
考虑这条边如果构成左转关系就继续压栈，如果构成右转关系就弹栈
如图，不断弹栈直到构成左转关系（左转右转可以用叉积来判断）
最后就是：
复杂度O(nlogn)
旋转卡壳：
传说中有24种读音的算法（逃~
要做的就是求对踵点的最大值吧......
我理解的对踵点是酱的：
然后就是，先求出一条边所对应的点，然后依次旋转就行
点的变化就是，while(更优) move;
凸包合并：
首先考虑两个凸包肯定是已经按极角排好序的
所以我们可以采取类似归并排序的思想将所有点排序
然后直接用栈求凸包就可以了
三角剖分：
鬼知道这是干什么的系列
定义：简单来讲就是把点集表示为若干三角形拼起来
算法叫Delaunay三角剖分，以下是两种具体实现方法
洋葱三角剖分：
http://blog.csdn.net/bo_jwolf/article/details/11985653
就是对点集不断求凸包然后将凸包删掉继续求：
然后·对于一个环其三角剖分为：
做法使用旋转卡壳实现的，看前面贴出来的dalao博客吧
P.S.听说洋葱皮(多次求凸包)可以O(nlogn)做，然而我不会QAQ
螺旋三角剖分：
不会（感觉会洋葱就够了吧QAQ）
http://blog.csdn.net/bo_jwolf/article/details/11985627
半平面交：
http://www.cnblogs.com/XDJjy/archive/2013/09/13/3320205.html
http://blog.csdn.net/non_cease/article/details/7796834
定义：每个半平面可以表示为Ax+By+C >(=) 0的形式
半平面交即为满足所有约束条件的二维区域，可用于求解多边形的内核 && 求凸包
做法：①每次考虑一个半平面对其他所有半平面的影响，O(n2)
②考虑分治，递归直到只剩可以直接求凸包的半平面数
运用上文提到的合并凸包的方法求解
③排序增量法 by zzy
1) 按向量的极角排序，对于极角相同的只留一个（用叉积实现）
2) 开一个双端队列 deque <int> q，放入前两个半平面
3) 考虑每次加入一个新的半平面，用新的半平面去更新这个队列：
while(顶部的两个半平面的交点在新半平面外) pop_front();
while(底部的两个半平面的交点在新半平面外) pop_back();
队头加入当前半平面 q.push_front(i)
不断用顶弹底&底弹顶：
while(可以弹) {
while (顶部的两个半平面的交点在底部的半平面外) pop_front();
while (底部的两个半平面的交点在顶部的半平面外) pop_back();
}
4) 如果deque中有元素则说明存在半平面交
若求的是多边形的核之类的，那么deque中的半平面交必须是封闭的，否则无解
若求的是纯半平面交，那就根据数据范围增加4个半平面再做，一样可以保证有界
若要具体求出凸包是哪些点就求一下q[i]和q[i-1]的交点以及q[1]与q[n]的交点即可
辛普森积分：
做法：每次判断左边+右边是否-lastans是否<eps，递归处理
公式：∫ (l~r) f(x)=(r-l)*(f(l)+f(r)+4*f(mid))/6
P.S.如果要求多边形的面积，f(i)就表示与直线x=i相交的多边形的截线长度和，直接暴力做即可
例：bzoj2178：http://www.lydsy.com/JudgeOnline/problem.php?id=2178
我的blog：http://www.cnblogs.com/xiaoxubi/p/6618272.html
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define eps 1e-13
using namespace std;
const int Mx=;
int n,tot,st,to;
bool vis[Mx];
double L[Mx],R[Mx];
struct Node { double x,y,r; } str[Mx];
struct Line { double l,r; } line[Mx];
double dis(Node a,Node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }
bool cmp1(Node a,Node b) { return a.r<b.r; }
bool cmp2(Node a,Node b) { return a.x-a.r<b.x-b.r; }
bool operator < (Line a,Line b) { return a.l<b.l; }
double cal(double fl,double fmid,double fr,double r_l) { return r_l*(fl+fr+*fmid)/; }
double get_f(double x)
{
double ans=; tot=;
for(int i=;i<=n;i++)
if(x>=L[i]&&x<=R[i])
{
double len=sqrt(str[i].r*str[i].r-(str[i].x-x)*(str[i].x-x));
line[++tot].l=str[i].y-len; line[tot].r=str[i].y+len;
}
sort(line+,line+tot+);
for(int i=,j;i<=tot;i++)
{
double minl=line[i].l,minr=line[i].r;
for(j=i+;j<=tot;j++)
{
if(line[j].l>minr) break;
if(line[j].r>minr) minr=line[j].r;
}
ans+=minr-minl; i=j-;
}
return ans;
}
double simpson(double l,double r,double mid,double fl,double fr,double fmid,double lastans)
{
double mid1=(l+mid)/,mid2=(mid+r)/,fmid1=get_f(mid1),fmid2=get_f(mid2);
double ans1=cal(fl,fmid1,fmid,mid-l),ans2=cal(fmid,fmid2,fr,r-mid);
if(fabs(ans1+ans2-lastans)<eps) return ans1+ans2;
return simpson(l,mid,mid1,fl,fmid,fmid1,ans1)+simpson(mid,r,mid2,fmid,fr,fmid2,ans2);
}
void solve()
{
double ans=0.00;
for(int i=,j;i<=n;i++)
{
st=i; double minl=L[i],minr=R[i],minmid;
for(j=i+;j<=n;j++)
{
if(L[j]>minr) break;
if(R[j]>minr) minr=R[j];
}
to=j-,i=to,minmid=(minl+minr)/;
double fl=get_f(minl),fr=get_f(minr),fmid=get_f(minmid),lstans=cal(fl,fmid,fr,minr-minl);
ans+=simpson(minl,minr,minmid,fl,fr,fmid,lstans);
}
printf("%.3lf",ans);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf%lf%lf",&str[i].x,&str[i].y,&str[i].r);
sort(str+,str++n,cmp1);
//剪枝
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(fabs(str[j].r-str[i].r)>=dis(str[j],str[i]))
{
vis[i]=; break;
}
for(int i=,tmp=,mx=n;i<=mx;i++) if(!vis[i]) str[++tmp]=str[i],n=tmp;
//
sort(str+,str++n,cmp2);
for(int i=;i<=n;i++) L[i]=str[i].x-str[i].r,R[i]=str[i].x+str[i].r;
solve();
return ;
}
后记：
就...就假装自己把数学方面的都总结完了吧QAQ......
博弈论的坑再说吧QAQ....不想再挖坑了QAQ
累死本宫了.....啊QAQ