排列组合板子A(n,m)C(n,m) ； 递推组合数公式 ； 杨辉三角

本文主要是介绍排列组合板子A(n,m)C(n,m) ； 递推组合数公式 ； 杨辉三角，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.直接求组合数：

组合数C(n,m)，n个里面选m个，结果为$$\frac{n!/(n-m)!}{m!}$$（前者其实就是n* n-1*…*n-m+1，分子分母都是m个数相乘）

ksm快速幂求的是逆元。用的是费马小定理，适用于模数为素数的时候。

快速幂板子

（板子中a是阶乘数组，预处理一下）

a[0] = 1;
for(int i=1;i<=n+k;i++)a[i] = i*a[i-1]%mod;

ll ksm(int x, int y, int mod) 
{if (x == 1) return 1;ll res = 1, base = x;while (y) {if (y & 1) res = (res * base) % mod;base = (base * base) % mod;y >>= 1;}return res;
}
ll C(ll n, ll m, ll p)
{if (m > n)return 0;return ((a[n] * ksm(a[m], p - 2, p)) % p * ksm(a[n - m], p - 2, p) % p);
}
ll A(ll n, ll m, ll p)
{if (m > n)return 0;return (a[n] * ksm(a[n - m], p - 2, p)) % p;
}

2.递推组合数公式：

$$C(n,m)=C(n-1,m)+C(n-1,m-1)$$

我们拿出一个元素，剩下n-1个。要么在 n-1 里面选 m 个，要么这个加上 n-1 里面选 m-1 个

private static final int MX = 31;
private static final int[][] c = new int [MX][MX];static {c[0][0] = c[1][0] = 1;for(int i=1;i<MX;i++){c[i][0] = 1;for(int j=1;j<=i;j++){c[i][j] = c[i-1][j] + c[i-1][j-1];}}
}

// 1 1// 2 1 , 2 2// 3 1 , 3 2 , 3 3// 4 1 , 4 2 , 4 3 , 4 4

3.杨辉三角

上面这个递推结果正是杨辉三角。

// 1// 1 1// 1 2 1    // 1 3 3 1                 C(3,0) C(3,1) C(3,2)// 1 4 6 4 1               C(4,0) C(4,1) C(4,2)

力扣401周赛T2

​

这篇关于排列组合板子A(n,m)C(n,m) ； 递推组合数公式 ； 杨辉三角的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---