For the problem 567E - President and Roads

I think I finally got the idea what is the "modulo based hacking" is about (thread http://mirror.codeforces.com/blog/entry/19590?#comment-244040)

When counting number of ways in a graph within the given ranges we can easily get out of bounds of long long data type. Therefore we need some way to be able to count and compare numbers larger than ll. Ideally we need a full stack BigInt support, but what if we can find something simpler than that. The naive approach here is to pick some large prime number M and perform all operations modulo M. Unfortunately this approach is not working for all possible inputs and leads to collisions, since the two different numbers may still match and the solution can be exploited — i.e. modulo based hacking.

Here is the list of less exploitable approaches:

1. Use "Modulo Hash" — i.e. use more than 1 large prime number when counting and compare numbers. Match is when all modulus are equal. see 12361537

2. Use random prime number each time, so hacker doesn't know it ahead of time, see 12362068 ^)))

For the 566D - Restructuring Company

Basic Disjoint Set C++ implementation (w/o ranks) using int vector

class DisjointSet{ public:

    vector<int> parent;

    DisjointSet(int n): parent(n) { for(int i=0; i<n; i++) parent[i] = i; }

    void join(int a, int b) { parent[find(b)] = find(a); }

    int find(int a){ return a == parent[a] ? a : parent[a] = find(parent[a]); }

    bool check(int a, int b){ return find(a) == find(b); }
};

For the http://mirror.codeforces.com/contest/560/problem/E

Number of distinct ways (only Down and Right) modulo p in a grid of w and h cells is:

modC(w+h-2, h-1, p) , where

modC(n, k, p) = C(n, k) mod p = modFact(n, p) * ((modInvFact(k, p) * modInvFact(n-k, p) mod p) mod p

modFact(n+1, p) = modFact(n, p) * (n+1) mod p, where modFact(0, p) = 1

modInvFact(n-1, p) = modInvFact(n, p) * n mod p, where modInvFact(N, p) = modExp(modFact(N, p), p-2, p)

modExp(n, e, p):
    res = 1
    b = n mod p
    while e > 0
        if (e mod 2 == 1):
           res := (res * b) mod p
        e >>= 1
        b = (b * b) mod p
    return res