# PBinfo #3703 – Potter – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

În Hogwarts există o tablă de șah cu N linii și M coloane. Harry Potter a găsit plasate, de către Hagrid, T ture care apără fiecare linia și coloana pe care este așezată. El trebuie să plaseze în siguranță K pioni pe tablă, adică fără ca vreunul dintre ei să fie atacat de vreo tură. Tabla de șah din Hogwarts este specială deoarece în cadrul unei celule pot fi plasați chiar și mai mulți pioni simultan!

Cerința
Cunoscând toate aceste reguli, ajutați-l pe Harry Potter să determine în câte modalități poate plasa în siguranță toți cei K pioni pe tabla de șah.

Date de intrare
Fișierul de intrare potter.in conține pe prima linie patru numere naturale nenule N, M, T, K separate prin câte un spațiu, cu semnificațiile din enunț, iar pe următoarele T linii, perechi (i j) reprezentând linia și coloana unde este așezată fiecare tură.

Date de ieșire
Fișierul de ieșire potter.out conține un singur număr, reprezentând restul împărțirii la 1.000.000.007 a numărului de modalități distincte de a poziționa toți cei K pioni.

Restricții și precizări

1 ≤ N, M ≤ 2000
1 ≤ K ≤ 100.000
1 ≤ T ≤ N * M
Două modalități de așezare sunt distincte dacă există cel puțin o celulă cu număr diferit de pioni

Exemplu:
potter.in

2 3 1 3
1 1
potter.out

4
Explicație
Pe tablă Harry Potter poate așeza în siguranță cei trei pioni în căsuțele (2,2) și (2,3). În cadrul fiecăreia el poate așeza 0, 1, 2, sau 3 pioni.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("potter.in");
ofstream g("potter.out");
const int NMAX = 2e3 + 1;
const int MOD = 1e9+7;
int N, M, T, K;
bool Line[NMAX], Column[NMAX];
int empty_cells;
static inline void Read ()
{
    f.tie(nullptr);
    f >> N >> M >> T >> K;
    for(int i = 1; i <= T; ++i)
    {
        int L = 0, C = 0;
        f >> L >> C;
        Line[L] = 1, Column[C] = 1;
    }
    return;
}
static inline void Load ()
{
    int l = 0, c = 0;
    for(int i = 1; i <= N; ++i)
        if(Line[i])
            ++l;
    for(int i = 1; i <= M; ++i)
        if(Column[i])
            ++c;
    empty_cells = N * M - (l * M + c * N - l * c);
    return;
}
static inline int lgput (int n, int p)
{
    int ans = 1, aux = n;
    for(int i = 0; (1 << i) <= p; ++i)
    {
        if(p & (1 << i))
            ans = (1LL * ans * aux) % (1LL * MOD);
        aux = (1LL * aux * aux) % (1LL * MOD);
    }
    return ans;
}
static inline int Comb (int n, int k)
{
    if(n < k)
        return 0;
    if(n == k)
        return 1;
    int ans = 1;
    for(int i = 2; i <= n; ++i)
        ans = (1LL * ans * i) % (1LL * MOD);
    int inv_mod = lgput(ans, MOD - 2);
    int last_mod = inv_mod;
    for(int i = (n - 1); i >= 1; --i)
    {
        inv_mod = (1LL * last_mod * (i + 1)) % (1LL * MOD);
        if(i == k)
            ans = (1LL * ans * inv_mod) % (1LL * MOD);
        if(i == (n - k))
            ans = (1LL * ans * inv_mod) % (1LL * MOD);
        last_mod = inv_mod;
    }
    return ans;
}
static inline void Solve ()
{
    g << Comb(empty_cells - 1 + K, empty_cells - 1) << '\n';
    g.close();
    return;
}
int main()
{
    Read();
    Load();
    Solve();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3703)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3703/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3703/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)