组合数学常用内容——基础内容+莫比乌斯反演

本文主要是介绍组合数学常用内容——基础内容+莫比乌斯反演，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

组合数学常用公式

A(n,r)=n(n-1)…(n-r+1)=n!/(n-r)!C(n,r)=A(n,r)/r!=n!/((n-r)r!)C(n,r)=C(n,n-r)C(n,r)=C(n-1,r)+C(n-1,r-1)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)C(n,k)C(k,r)=C(n,r)C(n-r,k-r)C(n,k+1)=C(n,k)*(n-k)/(k+1)重复排列：n^r;可重复组合：C(n+r-1,r)不相邻组合：C(n-r+1,r)圆周排列：A(n,r)/r项链排列：A(n,r)/2r多重全排列（r1个a1,r2个a2……组成n位串）：n!/(r1!*r2!*…)多项式的n次方的某项系数：(a1+a2+…+at)^n=∑n!/(r1!r2!…rt!)*(a1^r1*a2^r2*…*at^rt)错排递归公式：f(i) = (i - 1) * (f(i - 1) + f(i - 2));  i >= 4 (f(0) = 0, f(1) = 0, f(2) = 1, f(3) = 2)
（错排：n个节点它们原来的位置为i，然后让你把它们从新排列使得它们都不在它们原来的位置上。）

组合数预处理

typedef long long ll;
const int MAXN = 42;
ll c[MAXN][MAXN];void init(){
    c[0][0]=1;
    for(int i=1;i<MAXN;i++){
        c[i][i]=c[i][0]=1;
        for(int j=1;j<MAXN;j++){
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
}

母函数

母函数讲解详见：
http://blog.csdn.net/vsooda/article/details/7975485

这里直接贴出我的模板，注释非常详细，知道母函数概念，下面的代码根据注释就可以理解了

int main(){int T;cin >> T;while (T--){int n, m, sub[10], num[10];//sub对应背包中的体积/重量，num对应背包中的价值int c1[41], c2[41];//c1存储系数，也就是方案数，c2存储运算中间数据提供给c1更新cin >> n >> m;

这篇关于组合数学常用内容——基础内容+莫比乌斯反演的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---