组合数学、
-排列组合数
----sum求
sum=sum*(m--)/i;
int c(int n,int m)//n下标，m上标
{
    int sum=1;
    for(int i=1;i<=m;i++)
        sum=sum*(n--)/i;
    return sum;
}
----二维数组递推（打表）
#define maxx 1000
int c[maxx+2][maxx+2];
void init()//递推打表
{
    memset(c,0,sizeof(c));
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<maxx;i++)
    {
        c[i][i]=c[i][0]=1;
        for(int j=0;j<i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j]);
        }
    }
}
---原始公式（单个）数字太大，用分子分母约分，优化
#define maxx 1000
int c[maxx+2][maxx+2];
void init()//递推打表
{
    if(m>n-m) 
        m=n-m; 
    int temp=n; 
    for(int i=1;i<=m;i++)//根据组合公式把原始的分子分母分别存在数组中 
    { 
        up[i]=temp--; 
        down[i]=i; 
    } 
    for(int i=1;i<=m;i++)//外层循环代表分母，对分母依次进行约分 
        for(int j=1;j<=m;j++) 
        { 
            temp=gcd(down[i],up[j]); 
            if(temp>1) 
            { 
                up[j]/=temp; 
                down[i]/=temp; 
            } 
            if(down[i]==1)//分母已经为1，退出，进行下一个分母的约分 
                break; 
        } 
    int sum=1; 
    for(int i=1;i<=m;i++) 
        sum=sum*up[i]/down[i]; 
    return sum;
}
-全排列模板
-----生成全排列函数
prev_permutation和next_permutation
int main ()
{
    int a[] = {1,2,3};
    do
    {
        cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    }while(next_permutation(a,a+3));// 后一个排列组合

    return 0;
}
区别prev_permutation //前一个排列组合
--母函数
模板---用的时候一般会变一下数，式子中等阶指数（xiayige）
--错排
错位排列的公式有
dn=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
还有一个递推的形式
d[n]=(n-1)*(d[n-1]+d[n-2])
void D() 
{ 
    for(int i=2;i<=20;i++) 
        d[i]=(i-1)*(d[i-1]+d[i-2]); 
} 
---卡特兰数
卡特兰数：
 1 通项公式：
h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!)
 2递推公式:
h(n)=((4*n-2)/(n+1))*h(n-1); h(n)
       =h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0).
3前几项为：h(0)=1,h(1)=1,h(2)=2,h(3)=5,h(4)=14,h(5)=42,......

欧拉函数
φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),
其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1
求单个（公式地推）
int phi(int n)//求phi(n)
{
    int m=(int)sqrt(n+0.5);
    int ans=n;
    for(int i=2;i<=m;i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
打表（筛法）
#define maxn 32768
int phi[maxn];
void phi_table(int n)
{
    for(int i=2;i<=n;i++)
        phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
        for(int j=i;j<=n;j+=i)
        {
            if(!phi[j])
                phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
}
背包
01
c[i][m]=max{c[i-1][m],c[i-1][m-w[i]]+p[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入重量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为c[i-1][m]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的重量为m-w[i]的背包中”，此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。