Cod sursa(job #2460567)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 23 septembrie 2019 22:10:50
Problema Dirichlet Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#define ll long long
#define mod 9999991

using namespace std;
ifstream f("dirichlet.in");
ofstream g("dirichlet.out");
ll n;
ll logpow(ll a, ll b)
{
    ll rez = 1;
    while(b)
    {
        if(b & 1)
            rez = (rez * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return rez;
}
ll invers(ll x)
{
    return logpow(x, mod - 2) % mod;
}
ll fact(ll x)
{
    ll rez = 1;
    for(ll i = 1; i <= x; ++i)
        rez = (rez * i) % mod;
    return rez;
}

int main()
{
    f >> n;
    ll fact2n = fact(2 * n);
    ll factnminus = fact(n - 1);
    ll factn = (factnminus * n) % mod;
    ll factn1 = (factn * (n + 1) ) % mod;

    ll rez1 = (fact2n * invers(factn) ) % mod;
    rez1 = (rez1 * invers(factn) ) % mod;


    ll rez2 = (fact2n * invers(factnminus) ) % mod;
    rez2 = (rez2 * invers(factn1) ) % mod;
    g << (rez1 - rez2 +  mod) % mod;
    f.close();
    g.close();
    return 0;
}