北京培训记day1

时间:2024-01-07 09:14:08

感觉我所有博客也就这篇比较全了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

     更相减损→辗转相除

     北京培训记day1

二、逆元

  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出现循环

    如图:

      北京培训记day1

六、知识点补充

  ①:整除

    北京培训记day1

  ②:取模

    (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点阵可见点数

    北京培训记day1

  二项式反演:①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

               北京培训记day1

            Q3

              北京培训记day1

十二、线性代数

   ①行列式:例,对于矩阵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条边的无向图,求生成树计数

           例:对于下图

           北京培训记day1

           邻接矩阵存图:map[i][j]表示i与j之间边数的相反数

                  map[i][i]表示点i的度数

               北京培训记day1

                  求行列式,即为答案

                  即将矩阵化为三角形矩阵后求对角线乘积即可

                  P.S.将矩阵的某一行同时除以某个数,行列式的值不变。

                    矩阵的某两行相交换,行列式的值取相反数。

   ③矩阵乘法:1)有向图从i到j走k步的方案数:

          北京培训记day1

          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

      例:斐波那契数列

          北京培训记day1

十三、置换群

   ①概念: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引理

    北京培训记day1

    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))

十四、泰勒展开

   公式:

     北京培训记day1

   解释:

     感性的理解一下,对于一个多项式,求导得到的是每一项的系数,这样做显然是正确的

     而对于非多项式可以用多项式拟合(逃~

   多项式版本(牛顿二项式定理):

     P.S.感觉我这写的好乱啊QAQ

      北京培训记day1

   常见函数的泰勒展开式(非多项式):

      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

斐波那契数列

   通项公式:

        北京培训记day1

   前缀和:∑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:生成勾股数

        北京培训记day1

卡特兰数

   递推式: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允许空)

          北京培训记day1

          不同盒子相同球:插隔板,C(n-1,m)

          相同盒子相同球:整数划分,dp,f(n,m)=f(n-m,m)+f(n,m-1)

                       f(n,m)表示将n划分为不超过m的若干个整数

       通项公式:北京培训记day1

         通项公式可用容斥原理推导

       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为质数

  通项公式:北京培训记day1,Dobinski公式:期望值为1的泊松分布的n次矩

       北京培训记day1,即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.调和级数是发散的

伯努利数

  定义:北京培训记day1

  性质:①∑(k from 0 to n) C(n,k)*B(k) =0

        可以用递推求各项,递推式:

      北京培训记day1

      可以围观dalao博客:http://blog.csdn.net/acdreamers/article/details/38929067

      也可以O(nlogn)递推,用指数母函数展开然后balabala.....

      就是将定义中的e^x泰勒展开一下然后,搞成了这么个东西

        北京培训记day1

      然后你把分母多项式在%pow(x,n+1)意义下求个逆,%pow(x,n+1)就是将Bn以上的项都消掉

      然后对于x^i其系数就是Bi啦!(终于搞定了QAQ)

     ②B(0)=1,B(1)=-1/2

      B(k)=0,k为奇数

  用途:根据公式

     北京培训记day1

     O(k^2)预处理每一部分,可以在每个case以O(k)求出∑ i^k

      若k特别大也可以O(klogk)预处理,每个case O(klogk)

默慈金数

  http://blog.csdn.net/acdreamers/article/details/41213667

  递推式:北京培训记day1

      北京培训记day1

  应用:①在圆上的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

     北京培训记day1

     然后两边*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)

     如:

      北京培训记day1

       北京培训记day1

     考虑对原多项式也做类似的处理:将x变为1/x并在等式左右同乘x^n

     P.S.我们可以把R看成m阶多项式

     即:

       北京培训记day1

     我们发现,D(x)的系数不会大于n-m,又因为RR的系数为n-m+1,那么RR即可消掉

     即:

       北京培训记day1

     对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/ACMaker

       http://blog.csdn.net/hanchengxi/article/details/8639476

     定义:对于一个点集S,找出其中最小的一个子集S',对于S'的两个相邻顶点的边,所有点都在边的同一侧

        如:

          北京培训记day1

     做法:

        Graham扫描算法

          先找出左下角的点(肯定在凸包上),考虑如何找下一个点

          利用向量叉积的正负来判断,用一个栈来维护

          先按极坐标排序,将第一个点入栈然后向下一个点连边

          考虑这条边如果构成左转关系就继续压栈,如果构成右转关系就弹栈

          如图,不断弹栈直到构成左转关系(左转右转可以用叉积来判断)

          北京培训记day1

          最后就是:

          北京培训记day1

          复杂度O(nlogn)

     旋转卡壳:

       传说中有24种读音的算法(逃~

       要做的就是求对踵点的最大值吧......

       我理解的对踵点是酱的:

           北京培训记day1

       然后就是,先求出一条边所对应的点,然后依次旋转就行

       点的变化就是,while(更优) move;

     凸包合并:

       首先考虑两个凸包肯定是已经按极角排好序的

       所以我们可以采取类似归并排序的思想将所有点排序

       然后直接用栈求凸包就可以了

     三角剖分:

       鬼知道这是干什么的系列

       定义:简单来讲就是把点集表示为若干三角形拼起来

       算法叫Delaunay三角剖分,以下是两种具体实现方法

       洋葱三角剖分:

         http://blog.csdn.net/bo_jwolf/article/details/11985653

         就是对点集不断求凸包然后将凸包删掉继续求:

           北京培训记day1

         然后·对于一个环其三角剖分为:

          北京培训记day1

         做法使用旋转卡壳实现的,看前面贴出来的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