Cod sursa(job #2466932)

Utilizator razviii237Uzum Razvan razviii237 Data 3 octombrie 2019 11:44:12
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("functii.in");
ofstream g("functii.out");

const int mod = 30103, maxn = 1e4+5;

int n, s;

int pwr(int x, int y) {
    if(y == 0) { return 1; }
    if(y == 1) { return x; }
    int half = pwr(x, y / 2);
    if(y % 2 == 0) {
        return (half * half) % mod;
    } else {
        return (half * half * x) % mod;
    }
}

struct xy { int x, y; };
int fact[maxn];

xy ee(int a, int b) {
    if(b == 0) {
        return {1, 0};
    }
    xy ls = ee(b, a % b);
    return {ls.y, ls.x - (a / b) * ls.y};
}

int im(int x) {
    int r = ee(x, mod).x;
    r = (r + mod) % mod;
    return r;
}

int comb(int n, int k) {
    return (((fact[n] * im(fact[k])) % mod) * im(fact[n - k])) % mod;
}
int query(int n, int k) {
    return comb(n, k);
}

int main()
{
    f >> n >> s;

    fact[0] = 1;
    for(int i = 1; i <= n; i ++) {
        fact[i] = fact[i-1] * i;
        fact[i] %= mod;
    }

    int ans = pwr(2, s) - 2;

    ans *= query(n, n - s);
    ans %= mod;

    g << ans << '\n';

    f.close(); g.close();
    return 0;
}