Cod sursa(job #3258001)

Utilizator ninja_legend_11Vlad Marin-Perianu ninja_legend_11 Data 20 noiembrie 2024 15:07:32
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MOD 30103

using namespace std;

ifstream fin("functii.in");
ofstream fout("functii.out");

int64_t n, s, k, P, inv, ins;

int64_t putere(int64_t A , int64_t n)
{
    P = 1;
    while(n)
    {
        if(n%2) P = (P*A)%MOD;
        A = (A*A)%MOD;
        n /= 2;
    }
    return P;
}

int64_t factorial(const int64_t st, const int64_t dr)
{
    P = 1;
    for(k=st; k <= dr; k++) P = (P*k)%MOD;
    return P;
}

void gcd(int64_t &x, int64_t &y, int64_t a, int64_t b)
{
     if(!b)  x = 1, y = 0;
     else
     {
         gcd(x, y, b, a%b);
         P = x;
         x = y;
         y = P-y*(a/b);
     }
}

int64_t combinari(const int64_t x, const int64_t y)
{
    if(!y) return false;
    inv = 0;
    gcd(inv, ins, factorial(2, x-y), MOD);
    if(inv <= 0) inv = MOD+inv%MOD;
    return factorial(y+1, x)*inv%MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin >> n >> s;
    fout << (n > s ? (int64_t)(combinari(n, s)*(putere(2, s)-2))%MOD : 0);
}