在这个问题中,我们得到两个正数n和m(n <= m),分别是两组的项目总数。我们的任务是找到从这些集合的项目中选择对(一个或多个)的方法总数。
让我们举个例子来了解这个问题,
2 2
输出结果
6
我们有两个都有两个元素的集合
Set A = {1, 2} Set B = {3, 4}
一次排列一对的方式(1..3),(1 ... 4),(2..3),(2 ... 4)
一次排列两对的方式(1 ... 3,2 ... 4),(1 ... 4,2 ... 3)
为了解决这个问题,我们将使用集合元素的组合。以下是可以找到计数的简单组合公式。
Ways = Σn i=1n Ci* mCi* i! = Σni=1 ( nPi * mPi) /i
显示我们解决方案实施情况的程序,
#include <iostream> using namespace std; int* fact, *inverseMod; const int mod = 1e9 + 7; int power(int x, int y, int p){ int res = 1; x = x % p; while (y) { if (y & 1) res = (1LL * res * x) % p; y = y >> 1; x = (1LL * x * x) % p; } return res; } void calculate(int n){ fact[0] = inverseMod[0] = 1; for (int i = 1; i <= n; ++i) { fact[i] = (1LL * fact[i - 1] * i) % mod; inverseMod[i] = power(fact[i], mod - 2, mod); } } int nPr(int a, int b) { return (1LL * fact[a] * inverseMod[a - b]) % mod; } int selectPairCount(int n, int m){ fact = new int[m + 1]; inverseMod = new int[m + 1]; calculate(m); int ans = 0; for (int i = 1; i <= n; ++i) { ans += (1LL * ((1LL * nPr(n, i) * nPr(m, i)) % mod) * inverseMod[i]) % mod; if (ans >= mod) ans %= mod; } return ans; } int main() { int n = 2, m = 2; cout<<"The number of ways to select pairs is : "<<selectPairCount(n, m); return 0; }
输出结果
The number of ways to select pairs is : 6