Cod sursa(job #2374947)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 7 martie 2019 21:24:30
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>

FILE* FIN=freopen("functii.in","r",stdin);
FILE* FOUT=freopen("functii.out","w",stdout);

int n,s,sol;

void cit()
{
    scanf("%d%d",&n,&s);
}
int p2()
{
    int i;
    for(i=1,sol=1;i<s;i++)
    {
        sol*=2;
        sol%=30103;
    }
    sol*=2;
    sol-=2;
    sol%=30103;
    return sol;
}
int fact(int sr,int sp)
{
    int i,sl=1;
    for(i=sr;i<=sp;i++)
    {
        sl*=i;
        sl%=30103;
    }
    return sl;
}
void invmod(int &x,int &y,int z,int r)
{
    if(!r)
    {
        x=1;
        y=0;
    }
    else
    {
        int b;
        invmod(x,y,r,z%r);
        b=x;
        x=y;
        y=b-y*(z/r);
    }
}
void play()
{
    int mr,mc,invf,hlp;
    mr=(s>(n-s))*s+(s<(n-s))*(n-s);
    mc=(s<(n-s))*s+(s>(n-s))*(n-s);
    sol=p2();
    sol*=fact(mr+1,n);
    invmod(invf,hlp,fact(2,mc),30103);
    invf%=30103;
    invf+=(invf<0)*30103;
    sol*=invf;
}
void af()
{
    printf("%d",sol%30103);
}
int main()
{
    cit();
    play();
    af();
    return 0;
}