Cod sursa(job #1710694)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 29 mai 2016 17:16:12
Problema Padure2 Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MP make_pair
const int N = 1005;
const int M = 2000005;
const int con = 1000000007;
int mas[M],mas1[M];
pair <int,int> a[N];
int fun[N];
int c(int n,int m)
{
    return (ll)mas1[n + m] * mas[m] % con * mas[n] % con;
}
int main()
{
    freopen("padure2.in","r",stdin);
    freopen("padure2.out","w",stdout);
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);
    mas1[1]=mas1[0]=1,mas[0] = 1;
    int m = h + w;
    for (int i = 2; i <= m; i++) mas1[i] = ll(con / i) * (con - mas1[con % i]) % con;
    for (int i = 1; i <= m; i++) mas[i] = (ll)mas[i - 1] * mas1[i] % con;
    for (int i = 2; i <= m; i++) mas1[i] = (ll)mas1[i - 1] * i % con;
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    a[++n] = MP(h, w);
   	 sort(a+1,a+n+1);
    for (int i = 1; i <= n; i++)
	{
  	  for (int j = 1; j <= i - 1; j++)
      	   	if (a[j].second <= a[i].second) fun[i] = (-c(a[i].first - a[j].first,a[i].second - a[j].second) * ll(fun[j]) + fun[i]) % con;
   	  fun[i]=(fun[i]+c(a[i].first-1,a[i].second-1)+con)%con;
    }
    printf("%d",fun[n]);
}