组合数

2023-09-26 17:40:52

组合数

一、递推法求组合数 \(O(n)\)

\(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\)

可以理解为 n个取m的所有情况数 可以分解为 n-1中的取m个 与 n-1中取m-1个 的情况数相加，也就是第n个取与不取的两种情况数和

//递推求组合数 
const int N = 2005, MOD = 1e9 + 7;
int c[N][N];
void cn()
{
		for(int i = 0; i < N; i ++)
			for(int j = 0; j <= i; j ++)
				if(!j) 
					c[i][j] = 1;
				else 
					c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		while(n --)
		{
			int a, b;
			cin >> a >> b;
			cout << c[a][b] << endl;
		}
}

二、预处理逆元求组合数 \(O(nlogn)\)

组合数公式：\(C_n^m=\frac{n!}{m!(n-m)!}\)

我们知道在除法取余下，除以一个数，就等于乘上这个数的逆元，因此只需要乘上\(m!(n-m)!\)的逆元即可，求逆元可以用费马小定理+快速幂

// //组合数公式 + 逆元 求组合数
const int N = 100010, MOD = 1e9 + 7;
int fact[N], infact[N]; //阶乘、阶乘的逆元
void cn()
{
	fact[0] = infact[0] = 1;
	for(int i = 1; i < N; i ++)
	{
		fact[i] = (ll) fact[i - 1] * i % MOD;
		infact[i] = (ll)infact[i - 1] * ksm(i, MOD - 2, MOD) % MOD;
	}
	
	while(n --)
	{
		int a, b;
		cin >> a >> b;
		cout << (ll)fact[a] * infact[b] % MOD * infact[a - b] % MOD << endl;
	}
}

三、Lucas 卢卡斯定理

\(C_a^b=C_{a\,mod\,p}^{b\,mod\,p}\cdot C_{a/p}^{b/p}\,(mod\,p)\)

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);++i)
#define per(i,b,a) for (int i=(b);i>=(a);--i)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define itt iterator
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
#define fi first
#define se second
#define mp make_pair
#define MOD 1000000007
typedef vector<int> vii;
typedef vector<long long> vll;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> si;
typedef set<ll> sll;
const pii movee[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll ksm(ll a, ll b, ll p) {if (b == 0) return 1; ll ns = ksm(a, b >> 1, p); ns = ns * ns % p; if (b & 1) ns = ns * a % p; return ns;}		
const int MAXN = 0x7fffffff;

ll p;

//C(a, b)定义 + 逆元求解C(a, b)
ll C(ll a, ll b, ll p) 
{ 
	ll res = 1;
	for(int i = 1, j = a; i <= b; i ++, j --)
	{
		res = res * j % p;
		res = res * ksm(i, p - 2, p) % p;
	}
	return res % p;
}

//卢卡斯定理
ll lucas(ll a, ll b, ll p)
{
	if(a < p && b < p) return C(a, b, p);
	return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main ()
{	
	//IOS;
	int n;
	cin >> n;
	while(n --)
	{
		ll a, b, p;
		cin >> a >> b >> p;
		cout << lucas(a, b, p) << endl;
	}
	return 0;
}	
/*

*/

四、分解质因数+高精度求组合数（无取模）

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);++i)
#define per(i,b,a) for (int i=(b);i>=(a);--i)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define itt iterator
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
#define fi first
#define se second
#define mp make_pair
#define MOD 1000000007
typedef vector<int> vii;
typedef vector<long long> vll;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> si;
typedef set<ll> sll;
const pii movee[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll ksm(ll a, ll b, ll p) {if (b == 0) return 1; ll ns = ksm(a, b >> 1, p); ns = ns * ns % p; if (b & 1) ns = ns * a % p; return ns;}		
const int MAXN = 0x7fffffff;
const int N = 5010;
int sum[N];
bool st[N];

const int plim = 1e6 + 5;
ll prime[plim];
bool isnprime[plim];
ll pcnt = 0;
void getprime(int n)
{
	isnprime[1] = 1;
	for(int i = 2; i <= n; i ++)
	{
		if(!isnprime[i]) prime[++pcnt] = i;
		for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
		{
			isnprime[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}

vector <int> mul(vector <int> a, int b)
{
    vector <int> c;
    int t = 0;
    for(int i = 0;i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    // while(C.size()>1 && C.back()==0) C.pop_back();
    return c;
}

int get(int n, int p)
{
	int res = 0;
	while(n)
	{
		res += n / p;
		n /= p;
	}
	return res;
}

int main ()
{	
	//IOS;
	int a, b;
	cin >> a >> b;
	getprime(a);
	for(int i = 1; i <= pcnt; i ++)
	{
		int p = prime[i];
		sum[i] = get(a, p) - get(a - b, p) - get(b, p);
	}
	vector <int> res;
	res.push_back(1);
	for(int i = 1; i <= pcnt; i ++)
		for(int j = 0; j < sum[i]; j ++)
			res = mul(res, prime[i]);

	for(int i = res.size() - 1; ~i; i --)
		cout << res[i];
	cout << endl;
	return 0;
}	
/*

*/

卡特兰数\(C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n +1}\)

889. 满足条件的01序列 - AcWing题库

具体可见题解AcWing 889. 满足条件的01序列 - AcWing

代码示例：

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);++i)
#define per(i,b,a) for (int i=(b);i>=(a);--i)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define itt iterator
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
#define fi first
#define se second
#define mp make_pair
#define MOD 1000000007
typedef vector<int> vii;
typedef vector<long long> vll;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> si;
typedef set<ll> sll;
const pii movee[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll ksm(ll a, ll b, ll p) {if (b == 0) return 1; ll ns = ksm(a, b >> 1, p); ns = ns * ns % p; if (b & 1) ns = ns * a % p; return ns;}		
const int MAXN = 0x7fffffff;

int main ()
{	
	//IOS;
	int n;
	cin >> n;
	
	int res = 1;
	
	for(int i = 2 * n; i > n; i --) 
		res = (ll)res * i % MOD;

	for(int i = 1; i <= n; i ++)
		res = (ll)res * ksm(i, MOD - 2, MOD) % MOD;

	res = (ll)res * ksm(n + 1, MOD - 2, MOD) % MOD;

	cout << res << endl;
	
	return 0;
}	
/*

*/
上一篇：springboot集成swagger，通用流行框架大全


下一篇：webrtc ns模块代码公式详细解读