資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律研究在 C++ 中從兩個不同的集合中選擇一個或多個對的方法
在此問題中，我們得到了兩個正數 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
更新於：17-Jul-2020
126 觀看
廣告