Cod sursa(job #3249819)

Utilizator DunareTanasescu Luca-Ioan Dunare Data 17 octombrie 2024 23:17:59
Problema Combinari Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
const long long MOD = 1000000007;

void bezout(long long &x, long long &y, long long &d, int a, int b)
{
    if(!b)
        x = 1, y = 0, d = a;
    else
    {
        bezout(x, y, d, b, a % b);
        ///swap(x,y);
        x ^= y;
        y ^= x;
        x ^= y;
        y = y - x * (a / b);
        /*
         int aux = x;
         x = y;
         y = aux - y * (a / b);*/
    }
}
long long comb(long long n, long long k)
{
    long long x = 0, y = 0, d, valcomb = 1;
    for(int i = n - k + 1; i <= n; i++)
        valcomb=(valcomb*i)%MOD;
    for(int i = 1; i <= k; i++)
    {
        x=y=0;
        bezout(x, y, d, i, MOD);
        if(x <= 0)
            x = MOD - abs(x) % MOD;
        valcomb=(valcomb*x)%MOD;
    }
    return valcomb%MOD;
}
int main()
{
    long long  n, k ;
    f >> n >> k;
    g << comb(n,k);

    return 0;
}