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ă din k elevi?
• în parcul auto al unei firme de taxi sunt n mașini. Într-o zi vin la lucru k șoferi. În câte moduri pot fi alese cele k mașini folosite?
• la o masă sunt n locuri. La masă vor sta k persoane. În câte moduri putem alege scaunele folosite?
• avem n bomboane diferite. În câte moduri putem alege k bomboane?
• o mulțime are n elemente. Câte submulțimi cu k elemente are?
• etc.

Din lipsă de imaginație, cerința este:

Se dau numerele naturale n și k. Calculați $C_n^k$.

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 $C_n^k$.

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);
}