HackerRank Combinatorics – Strongly Connected Digraphs

Challenge: Strongly Connected Digraphs

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464815861

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/strongly-connected-digraphs/problem

Cerinta

Count the number of [labeled strongly connected digraphs](http://en.wikipedia.org/wiki/Directed_graph) with the given number of vertices.  

**Input Format**  
The first line contains $T$, the number of queries.  
Following are $T$ lines. Each line contains one integer $N$, denoting the number of vertices.  

**Output Format**  
Output $T$ lines. Each line is the number of labeled strongly connected digraphs with $N$ vertices, modulo $(10^9 + 7)$. 

**Constraints**  
$1 \le T \le 1000$  
$1 \le N \le 1000$  

**Sample Input**

	5
	1
	2
	3
	4
	1000

**Sample Output**

	1
	1
    18
    1606
    871606913

**Explanation**

You can refer to [oeis](http://oeis.org/A003030).

Cod sursa

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

static inline int addm(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
static inline int subm(int a, int b) {
    a -= b;
    if (a < 0) a += MOD;
    return a;
}
static inline int mulm(long long a, long long b) {
    return (int)((a * b) % MOD);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    vector<int> q(T);
    int Nmax = 0;
    for (int i = 0; i < T; ++i) {
        cin >> q[i];
        Nmax = max(Nmax, q[i]);
    }

    int maxPow = Nmax * (Nmax - 1);
    vector<int> pow2(maxPow + 1, 1);
    for (int i = 1; i <= maxPow; ++i) pow2[i] = addm(pow2[i - 1], pow2[i - 1]);

    vector<vector<int>> C(Nmax + 1, vector<int>(Nmax + 1, 0));
    for (int n = 0; n <= Nmax; ++n) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k) C[n][k] = addm(C[n - 1][k - 1], C[n - 1][k]);
    }

    vector<int> b(Nmax + 1, 0), a(Nmax + 1, 0);
    if (Nmax >= 1) {
        b[1] = 1;
        a[1] = 1;
    }

    for (int n = 2; n <= Nmax; ++n) {
        int val = pow2[n * (n - 1)];
        for (int j = 1; j <= n - 1; ++j) {
            int term = mulm(C[n][j], mulm(pow2[(n - 1) * (n - j)], b[j]));
            val = subm(val, term);
        }
        b[n] = val;
    }

    for (int n = 2; n <= Nmax; ++n) {
        int val = b[n];
        for (int j = 1; j <= n - 1; ++j) {
            int term = mulm(C[n - 1][j - 1], mulm(b[n - j], a[j]));
            val = addm(val, term);
        }
        a[n] = val;
    }

    for (int n : q) {
        cout << a[n] << '\n';
    }

    return 0;
}