Cod sursa(job #1710074)

Utilizator DEFINEtelyEngineersUPB Pirtoaca Vasilescu Zamfiratos DEFINEtelyEngineers Data 28 mai 2016 14:57:38
Problema Padure2 Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 2000001
#define KMAX 1001
#define MOD 2000003

vector < pair <int, int> > v, a;

inline void gcd(int a, int b, int &x, int &y)
{
    if(b==0) {
        x=1;
        y=0;
    }
    else {
        int x0,y0;
        gcd(b,a%b,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}

inline int inverse(int a)
{
	int x,y;
	gcd(a,MOD,x,y);
    while(x<=0) 
        x=x+MOD;
    if(x==MOD)
        x=0;
	return x;
}

int cnt[NMAX],fact[NMAX],inv[NMAX];

inline int number(int l1, int c1, int l2, int c2)
{
	int n = (l2 - l1);
	int m = (c2 - c1);
	return (1LL * ((1LL * fact[n + m] * inv[n])% MOD) * inv[m]) % MOD;
}

int main ()
{
	int n,m,k,i,x,y,j;
	ifstream f("padure2.in");
	ofstream g("padure2.out");
	f>>n>>m>>k;
	for(i=1;i<=k;i++) {
		f>>x>>y;
		a.push_back(make_pair(x,y));
	}
	f.close();
	a.push_back(make_pair(n,m));
	sort(a.begin(), a.end());
	
	for(i = 0; i <= k; i++) {
		int ok = 1;
		for(vector <pair <int, int> > :: iterator it = v.begin();it != v.end();it++)
			if(*it == a[i]) {
				ok = 0;
				break;
			}
		if(ok) 
			v.push_back(a[i]);
	}
	
	k = v.size();
	
	fact[0] = 1;
	inv[0] = 1;
	for(i = 1; i <= n + m; i++) {
		fact[i] = (1LL * i * fact[i - 1])%MOD;
		inv[i] = inverse(fact[i]);
	}
	
	for(i = 0; i < k; i++) {
		cnt[i] = number(1, 1, v[i].first, v[i].second);
		for(j = 0; j < i; j++) {
			if(v[j].first <= v[i].first && v[j].second <= v[i].second)
				cnt[i] = (cnt[i] - 1LL * (number(v[j].first, v[j].second, v[i].first, v[i].second))*cnt[j] % MOD + MOD)%MOD;
		}
	}
	
	g << cnt[k - 1] << '\n';
	g.close();
	return 0;
}