Cod sursa(job #2741084)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 15 aprilie 2021 14:49:44
Problema Padure2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.37 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MODULO = 2000003;

const int NMAX = 1000000;
const int CMAX = 1000;

long long fact[1 + NMAX];
long long combinari[CMAX];

vector<pair<int, int>> poz;

long long ridicareLog(long long baza, int exp)
{
    long long sol = 1;

    while (exp > 0)
    {
        if (exp % 2 == 1)
        {
            sol *= baza;
            sol %= MODULO;
        }

        baza *= baza;
        baza %= MODULO;

        exp /= 2;
    }

    return sol;
}

void calcFact()
{
    fact[0] = 1;

    for (int i = 1; i <= NMAX; i++)
    {
        fact[i] = fact[i - 1] * i;
        fact[i] %= MODULO;
    }
}

int calcComb(int n, int k)
{
    return (((fact[n] * ridicareLog(fact[k], MODULO - 2)) % MODULO) * ridicareLog(fact[n - k], MODULO - 2)) % MODULO;
}

bool comp(pair<int, int>& a, pair<int, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int main()
{
    ifstream in("padure2.in");
    ofstream out("padure2.out");

    calcFact();

    int n, m, c;

    in >> n >> m >> c;

    long long sol = calcComb(n + m - 2, (n + m) / 2 - 1 - abs(n - m) / 2);

    for (int i = 1; i <= c; i++)
    {
        int l, c;

        in >> l >> c;

        poz.emplace_back(l, c);
    }

    sort(poz.begin(), poz.end(), comp);

    for (int i = 0; i < poz.size(); i++)
    {
        int l = poz[i].first;
        int c = poz[i].second;

        combinari[i] = calcComb(l + c - 2, (l + c) / 2 - 1 - abs(l - c) / 2);

        for (int j = 0; j < i; j++)
        {
            int nRelativ = l - poz[j].first + 1;
            int mRelativ = c - poz[j].second + 1;

            combinari[i] -= (combinari[j] * calcComb(nRelativ + mRelativ - 2, (nRelativ + mRelativ) / 2 - 1 - abs(nRelativ  - mRelativ) / 2)) % MODULO;

            while (combinari[i] < 0)
                combinari[i] += MODULO;
        }

        if (l <= n && c <= m)
        {
            int nRelativ = n - l + 1;
            int mRelativ = m - c + 1;

            sol -= (combinari[i] * calcComb(nRelativ + mRelativ - 2, (nRelativ + mRelativ) / 2 - 1 - abs(nRelativ  - mRelativ) / 2)) % MODULO;

            while (sol < 0)
                sol += MODULO;
        }
    }

    out << sol << '\n';

    return 0;
}