# Cod sursa(job #1878286)

Utilizator Data 13 februarie 2017 23:42:01 Padure2 0 cpp done Arhiva ICPC 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;

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;
}
``````