Cod sursa(job #2435337)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 3 iulie 2019 17:56:07
Problema Padure2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 1.49 kb
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

typedef long long ll;
typedef long double ld;

ll n, m, k, A[1005], F[2000005];
pair<ll, ll> V[1005];

void gcd(ll &x, ll &y, ll a, ll b)
{
    if (!b)
        x = 1, y = 0;
    else
    {
        gcd(x, y, b, a % b);
        ll aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

ll inv(ll A)
{
    ll inv=0, ins;
    gcd(inv, ins, A, mod);
    if (inv <= 0)
        inv = mod + inv % mod;
    return inv % mod;
}

ll solve(ll x, ll y)
{
    return ((F[x+y-2] * inv(F[y-1]) %mod) * inv(F[x-1])) % mod;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    freopen("padure2.in", "r", stdin);
    freopen("padure2.out", "w", stdout);
    cin>>n>>m>>k;
    F[0]=1;
    for (int i=1; i<=2e6; i++)
        F[i] = (F[i-1]*i)%mod;
    ll sol = solve(n, m);
    for (int i=1; i<=k; i++)
    {
        cin>>V[i].first>>V[i].second;
    }
    sort(V+1, V+k+1);
    for (int i=1; i<=k; i++)
        A[i] = solve(V[i].first, V[i].second);
    for (int i=1; i<=k; i++)
    {
        sol -=  solve(n-V[i].first+1, m-V[i].second+1) * A[i] % mod;
        sol %= mod;
        if (sol < 0)
            sol+=mod;
        for (int j=i+1; j<=k; j++)
        {
            if (V[i].second>V[j].second) continue;
            A[j] -= solve(abs(V[i].first-V[j].first)+1, abs(V[i].second-V[j].second)+1) * A[i] %mod;
            A[j] %= mod;
            if (A[j]<0)
                A[j]+=mod;
        }
    }
    cout<<sol;
    return 0;
}