Cod sursa(job #1878286)

Utilizator misinoonisim necula misino Data 13 februarie 2017 23:42:01
Problema Padure2 Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.53 kb
#include<fstream>
#include<algorithm>

#define K 1010
#define N 2000100

#define x first
#define y second
#define MOD 2000003

using namespace std;

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

int i,j,n,k,m,sol[K],fact[N], inv[N];
pair<int,int> v[K];


int putere(int n, int p)
{
    int sol = 1, x = n;

    while(p)
    {
        if(p & 1)
        {
            --p;
            sol = (1LL * sol * x) % MOD;
        }
        else
            x = (1LL * x * x) % MOD,
            p >>= 1;
    }
}

void precalc_comb(int n)
{
    fact[0] = fact[1] = 1;

    for(i = 2; i <= n; ++i)
        fact[i] = (1LL *fact[i - 1] * i) % MOD;

    inv[n] = putere(fact[n], MOD - 2);

    for(i = n - 1; i >= 0; --i)
        inv[i] = (1LL * inv[i + 1] * (i + 1)) % MOD;
}

int comb(int n, int k)
{
    return (1LL * ((1LL * fact[n] * inv[k]) % MOD) * inv[n - k]) % MOD;
}

int main()
{
    f >> n >> m >> k;

    --n;
    --m;

    for(i = 1; i <= k; ++i)
    {
        f >> v[i].x >> v[i].y;
        --v[i].x;
        --v[i].y;
    }

    ++k;
    v[k].x = n;
    v[k].y = m;

    sort(v + 1, v + k + 1);

    precalc_comb(n + m);

    for(i = 1; i <= k; ++i)
    {
        sol[i] = comb(v[i].x + v[i].y, v[i].x);

        for(j = 1; j < i; ++j)
            if(v[j].x <= v[i].x && v[j].y <= v[i].y)
                sol[i] = (sol[i] + MOD - (1LL * comb(v[i].x + v[i].y - v[j].x - v[j].y, v[i].x - v[j].x) * sol[j]) % MOD) % MOD;
    }

    g << sol[k] << '\n';

    return 0;
}