250
Cerința
Această problemă ar putea avea oricare dintre următoarele cerințe:
- într-o clasă sunt
n
elevi. În câte moduri putem face o echipă dink
elevi? - în parcul auto al unei firme de taxi sunt
n
mașini. Într-o zi vin la lucruk
șoferi. În câte moduri pot fi alese celek
mașini folosite? - la o masă sunt
n
locuri. La masă vor stak
persoane. În câte moduri putem alege scaunele folosite? - avem
n
bomboane diferite. În câte moduri putem alegek
bomboane? - o mulțime are
n
elemente. Câte submulțimi cuk
elemente are? - etc.
Din lipsă de imaginație, cerința este:
Se dau numerele naturale n
și k
. Calculați Ckn.
Date de intrare
Programul citește de la tastatură numerele naturale n k
.
Date de ieșire
Programul va afișa pe ecran numărul C
, reprezentând Ckn.
Restricții și precizări
0 ≤ k ≤ n ≤ 500
Exemplu
Intrare
4 2
Ieșire
6
Explicație
Dacă o mulțime are 4
elemente, fie aceasta A={a,b,c,d}
, atunci submulțimile cu câte 2
elemente sunt {a,b}
, {a,c}
, {a,d}
, {b,c}
, {b,d}
, {c,d}
, adică 6
submulțimi.
#include <bits/stdc++.h> using namespace std; int n , k , v[1001]; void comb(int n , int k) { for(int i = 1 ; i <= k ; i++) v[i] = n - i + 1; for(int i = 1 ; i <= k ; i++) { int x = i , d = 2; while(x > 1) { if(x % d == 0) { int p = 0; for(int j = 1 ; j <= k ; j++) if(v[j] % d == 0) p = j; v[p] /= d; x /= d; } else d++; if(d * d > x) d = x; } } int r[1001]; r[0] = 1 , r[1] = 1; for(int i = 1 ; i <= k ; i++) { int t = 0; for(int j = 1 ; j <= r[0] ; j++) { int x = t + r[j] * v[i]; r[j] = x % 10; t = x / 10; } while(t) r[++r[0]] = t % 10 , t /=10; } for(int i = r[0] ; i > 0 ; i--) cout << r[i]; } int main() { cin >> n >> k; comb(n , k); }
Comentarii