Soluție HackerRank pentru Strongly Connected Digraphs, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…

  • Problemă: Strongly Connected Digraphs
  • Domeniu: Combinatorics
  • Limbaj: C++14

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

Cerință

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 ≤ T ≤ 1000
1 ≤ N ≤ 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 sursă

#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;
}
HackerRank Combinatorics – Strongly Connected Digraphs