Cod sursa(job #2148658)

Utilizator adiaioanaAdia R. adiaioana Data 1 martie 2018 21:12:33
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#define M 30103
using namespace std;
ifstream fin("functii.in");
ofstream fout("functii.out");
int n,s;
long long nr,p,c,v[3][10001];
long long comb(int n,int k);
long long power(int m,int e);
void triunghi();
int main()
{
    fin>>n>>s;
    triunghi();
    c=v[1][n-s+1]%M;
    p=(power(2,s)+M-2)%M;
    nr=(c*p)%M;
    fout<<nr<<'\n';
    return 0;
}
void triunghi()
{
    v[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=min(i+1,n-s+1);j++)
        {
            v[0][j]=v[1][j];
            v[1][j]+=v[0][j-1];
            v[1][j]=v[1][j]%M;
        }
}
long long power(int m,int e)
{
    if(e==0)
        return 1;
    long long x=power(m,e/2);
    if(e%2==1)
        return (((x*x)%M)*m)%M;
    else return (x*x)%M;
}