HackerRank Combinatorics – Highway Construction

Challenge: Highway Construction

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 75.0 / 75

Submission status: Accepted

Submission score: 1.0

Submission ID: 464762397

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/highway-construction/problem

Cerinta

You are planning the next FIFA World Cup and you are counting the number of highways that need to be built to connect the cities with the venue.  
Your country has $n$ cities and all cities lie on a single straight road called “Highway Road”. If you want to go from City $x$ to City $y$ ( where $x \leq y$ ), you need to go through city $x, x+1, x+2, \cdots , y-1, y$. 

The requirements for the highways are as follows:

1. All games will be held in the $n^{th}$ city.
2. New bidirectional roads, called _"Super Highways"_, need to be built such that it is possible to visit the $n^{th}$ city from any other city directly.  

You also have the cost to fulfil the second condition. The engineering team knows that if the length of a Super Highway is $l$, then it will cost $l^k$, where $k$ is an integer constant.The length of Super Highway between city $x$ and $y$ is $|x-y|$.  

For this problem, you need to find only a rough estimation of the cost, hence, find Total Cost Modulo $1000000009$.

Input Format

First line will contain a single positive integer $q$ denoting the number of queries. Then for each case there will be two positive integers, $n$ and $k$.

Output Format

For each case find the cost to build Super Highways such that it is possible to visit $n^{th}$ city from any other city directly. You have to print this value Modulo $1000000009$.

Constraints

+ $1 \leq q \leq 200$  
+ $1 \leq n \leq 10^{18}$  
+ $1 \leq k \leq 1000$

Cod sursa

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

static const long long MOD = 1000000009LL;

long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    if (a < 0) a += MOD;
    while (e > 0) {
        if (e & 1LL) r = (__int128)r * a % MOD;
        a = (__int128)a * a % MOD;
        e >>= 1LL;
    }
    return r;
}

long long sum_pows(long long m, int k) {
    if (m <= 0) return 0;

    int d = k + 2; // degree is k+1, need k+2 points
    vector<long long> y(d + 1, 0);
    for (int i = 1; i <= d; ++i) {
        y[i] = (y[i - 1] + modpow(i, k)) % MOD;
    }

    if (m <= d) return y[(int)m];

    vector<long long> fact(d + 1), invfact(d + 1);
    fact[0] = 1;
    for (int i = 1; i <= d; ++i) fact[i] = (__int128)fact[i - 1] * i % MOD;
    invfact[d] = modpow(fact[d], MOD - 2);
    for (int i = d; i >= 1; --i) invfact[i - 1] = (__int128)invfact[i] * i % MOD;

    long long x = m % MOD;
    vector<long long> pref(d + 2, 1), suf(d + 2, 1);
    for (int i = 0; i <= d; ++i) {
        long long t = (x - i) % MOD;
        if (t < 0) t += MOD;
        pref[i + 1] = (__int128)pref[i] * t % MOD;
    }
    for (int i = d; i >= 0; --i) {
        long long t = (x - i) % MOD;
        if (t < 0) t += MOD;
        suf[i] = (__int128)suf[i + 1] * t % MOD;
    }

    long long ans = 0;
    for (int i = 0; i <= d; ++i) {
        long long num = (__int128)pref[i] * suf[i + 1] % MOD;
        long long den_inv = (__int128)invfact[i] * invfact[d - i] % MOD;
        if ((d - i) & 1) den_inv = (MOD - den_inv) % MOD;
        long long term = (__int128)y[i] * num % MOD;
        term = (__int128)term * den_inv % MOD;
        ans += term;
        if (ans >= MOD) ans -= MOD;
    }
    return ans;
}

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

    int q;
    cin >> q;
    while (q--) {
        long long n;
        int k;
        cin >> n >> k;
        if (n <= 2) {
            cout << 0 << '\n';
            continue;
        }
        long long ans = (sum_pows(n - 1, k) - 1) % MOD; // skip distance-1 road (already exists)
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }
    return 0;
}