HackerRank Combinatorics – Costly Graphs

Challenge: Costly Graphs

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464834543

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/costly-graphs/problem

Cerinta

Let's define the _cost of a simple undirected graph_ as the sum of the costs of its nodes. The _cost of a node_ is defined as _D_<sup>_K_</sup>, where _D_ is its degree.

You are given _N_ and _K_. You need to find the sum of the costs of all possible simple undirected graphs with _N_ nodes. As this number may be very large, output the sum modulo _1005060097_.

**Definitions**  
Here are a few definitions from graph theory in case you're not familiar with them.

An _undirected graph_ is an ordered pair (_V_, _E_) consisting of a set _V_ of _nodes_, and a set _E_ of _edges_ which consists of unordered pairs of nodes from _V_.

The _degree_ of a node is the number of edges incident to it.

A _simple undirected graph_ is an undirected graph with no loops and multiple edges. A _loop_ is an edge connecting a node to itself. _Multiple edges_ are two or more edges connecting the same pair of nodes.


**Input Format**  
The first line contains the number of test cases _T_.   
Each of the next _T_ lines contains two integers _N_ and _K_ separated by a space.

**Output Format**  
For each test case, output one line containing the sum of the costs of all possible simple undirected graphs with _N_ nodes, modulo _1005060097_.


**Constraints**  
1 ≤ _T_ ≤ 2·10<sup>5</sup>  
1 ≤ _N_ ≤ 10<sup>9</sup>  
1 ≤ _K_ ≤ 2·10<sup>5</sup>  
The sum of the _K_'s in a single test file is at most 2·10<sup>5</sup>.

**Sample input**  

    5
    1 1
    2 3
    3 2
    6 5
    20 20


**Sample Output**  

    0
    2
    36
    67584000
    956922563

**Explanation**   
In the first case, there is only one simple graph with 1 node, and the cost of that graph is 0<sup>1</sup> = 0.

In the second case, there are two simple graphs with 2 nodes, one with a single edge and one with no edges.  
The cost of the graph with a single edge is 1<sup>3</sup>+1<sup>3</sup> = 2.  
The cost of the graph with no edges is 0<sup>3</sup>+0<sup>3</sup> = 0.  
Thus, the total is 2+0 = 2.

In the third case, there are eight simple graphs with 3 nodes.  
There is one graph with three edges, and its cost is 2<sup>2</sup>+2<sup>2</sup>+2<sup>2</sup> = 12.  
There are three graphs with two edges, and the cost of each is 1<sup>2</sup>+1<sup>2</sup>+2<sup>2</sup> = 6.  
There are three graphs with one edge, and the cost of each is 0<sup>2</sup>+1<sup>2</sup>+1<sup>2</sup> = 2.  
There is one graph with no edges, and its cost is 0<sup>2</sup>+0<sup>2</sup>+0<sup>2</sup> = 0.  
Thus, the total is 12·1 + 6·3 + 2·3 + 0·1 = 36.

Cod sursa

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

// Costly Graphs - HackerRank
// Sum over all simple graphs on N labeled vertices of sum_v deg(v)^K (mod P).

static const int MOD = 1005060097;     // required modulus
static const int PRIMITIVE_ROOT = 5;   // primitive root for MOD

static inline int mulmod(long long a, long long b) { return (int)((a * b) % MOD); }

static long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
static inline int mod_inv(int a) { return (int)mod_pow(a, MOD - 2); }

static void ntt(vector<long long>& a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = mod_pow(PRIMITIVE_ROOT, (MOD - 1) / len);
        if (invert) wlen = mod_pow(wlen, MOD - 2);

        for (int i = 0; i < n; i += len) {
            long long w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; j++) {
                long long u = a[i + j];
                long long v = a[i + j + half] * w % MOD;
                a[i + j] = u + v;
                if (a[i + j] >= MOD) a[i + j] -= MOD;
                a[i + j + half] = u - v;
                if (a[i + j + half] < 0) a[i + j + half] += MOD;
                w = w * wlen % MOD;
            }
        }
    }

    if (invert) {
        long long inv_n = mod_pow(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * inv_n % MOD;
    }
}

static vector<int> convolution(const vector<int>& a, const vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    int n1 = (int)a.size(), n2 = (int)b.size();
    int n = 1;
    while (n < n1 + n2 - 1) n <<= 1;

    vector<long long> fa(n), fb(n);
    for (int i = 0; i < n1; i++) fa[i] = a[i];
    for (int i = 0; i < n2; i++) fb[i] = b[i];

    ntt(fa, false);
    ntt(fb, false);
    for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
    ntt(fa, true);

    vector<int> res(n1 + n2 - 1);
    for (int i = 0; i < (int)res.size(); i++) res[i] = (int)fa[i];
    return res;
}

// F(n,k) = sum_{d=0..n} C(n,d) d^k (mod MOD)
// via Stirling S(k,t) and identity:
// sum_d C(n,d) (d)_t = (n)_t * 2^{n-t}
static int calc_F(long long n, int k, const vector<int>& fact, const vector<int>& invfact) {
    if (k == 0) return (int)mod_pow(2, n);

    // Stirling numbers S(k,t) computed by convolution:
    // S(k,t) = 1/t! * sum_{j=0..t} (-1)^{t-j} C(t,j) j^k
    // This equals convolution of sequences:
    // A[j] = j^k / j!, B[j] = (-1)^j / j!
    vector<int> A(k + 1), B(k + 1);
    for (int i = 0; i <= k; i++) {
        long long p = (i == 0 ? 0 : mod_pow(i, k)); // k>=1 in constraints
        A[i] = mulmod(p, invfact[i]);
        B[i] = invfact[i];
        if (i & 1) B[i] = (B[i] == 0 ? 0 : MOD - B[i]);
    }

    vector<int> stir = convolution(A, B); // stir[t] = S(k,t)

    int limit = (int)min<long long>(n, k);
    long long pow2 = mod_pow(2, n);
    long long inv2 = mod_inv(2);

    long long falling = 1; // (n)_0
    long long res = 0;

    for (int t = 0; t <= limit; t++) {
        long long s2 = (t < (int)stir.size()) ? stir[t] : 0;
        res += s2 * falling % MOD * pow2 % MOD;
        res %= MOD;

        if (t < limit) {
            falling = falling * ((n - t) % MOD) % MOD; // (n)_{t+1}
            pow2 = pow2 * inv2 % MOD;                  // 2^{n-(t+1)}
        }
    }

    return (int)res;
}

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

    int T;
    cin >> T;

    vector<long long> Ns(T);
    vector<int> Ks(T);
    int maxK = 0;

    for (int i = 0; i < T; i++) {
        long long N;
        int K;
        cin >> N >> K;
        Ns[i] = N;
        Ks[i] = K;
        maxK = max(maxK, K);
    }

    // factorials up to maxK
    vector<int> fact(maxK + 1), invfact(maxK + 1);
    fact[0] = 1;
    for (int i = 1; i <= maxK; i++) fact[i] = mulmod(fact[i - 1], i);
    invfact[maxK] = mod_inv(fact[maxK]);
    for (int i = maxK; i >= 1; i--) invfact[i - 1] = mulmod(invfact[i], i);

    for (int qi = 0; qi < T; qi++) {
        long long N = Ns[qi];
        int K = Ks[qi];

        if (N == 1) {
            cout << 0 << "\n";
            continue;
        }

        long long n = N - 1;
        long long exponent = n * (n - 1) / 2; // edges among the other vertices
        long long base = (N % MOD) * mod_pow(2, exponent) % MOD;

        int F = calc_F(n, K, fact, invfact);
        long long ans = base * F % MOD;
        cout << ans << "\n";
    }
    return 0;
}