HackerRank Algebra – Summing the K-N-R Series

Challenge: Summing the K-N-R Series

Subdomeniu: Algebra (algebra)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464763207

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/summing-the-k-n-r-series/problem

Cerinta

You are given a sequence whose $n^{\text{th}}$ term is  
$$T_n = n^K \times R^n$$
You have to evaluate the series
$$S_n = T_1 + T_2 + T_3 + \cdots + T_n$$
Find $S_n \bmod (10^9+7)$.

**Input Format**  

The first line of input contains $T$, the number of test cases.  
Each test case consists of three lines, each containing $K$, $n$ and $R$ respectively.  

**Output Format** 

For each test case, print the required answer in a line.  

**Constraints**  

$1 \le T \le 10$  
$1 \le K \le 10^{3}$  
$1 \le n \le 10^{16}$  
$2 \le R \le 10^{16}$  
$R\bmod (10^9 + 7) \not= 1$  

**Sample Input**  

	2
    2
    5
    2
    3
    4
    3
    
**Sample Output**  

	1146
    5988

**Explanation**  

Case 1: $1146 =  1^2\times 2^1   +   2^2\times 2^2   +   3^2\times 2^3   +   4^2\times 2^4   +   5^2\times 2^5$  
Case 2: $5988 = 1^3\times 3^1   +   2^3\times 3^2   +   3^3\times 3^3   +   4^3\times 3^4$

Cod sursa

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

static const long long MOD = 1000000007LL;

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;
}

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

    int T;
    cin >> T;
    while (T--) {
        int K;
        long long n, R;
        cin >> K >> n >> R;

        long long r = R % MOD;
        long long invr = modpow(r, MOD - 2);
        long long den = (1 - invr) % MOD;
        if (den < 0) den += MOD;
        long long invDen = modpow(den, MOD - 2);

        vector<vector<long long>> C(K + 1, vector<long long>(K + 1, 0));
        for (int i = 0; i <= K; ++i) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
                if (C[i][j] >= MOD) C[i][j] -= MOD;
            }
        }

        vector<long long> b(K + 1, 0); // P(x)=sum b[j] x^j
        for (int t = K; t >= 0; --t) {
            long long s = 0;
            for (int j = t + 1; j <= K; ++j) {
                long long coef = C[j][t];
                if ((j - t) & 1) coef = (MOD - coef) % MOD;
                s = (s + (__int128)b[j] * coef) % MOD;
            }
            long long rhs = (t == K ? 1 : 0);
            long long val = (rhs + (__int128)invr * s) % MOD;
            b[t] = (__int128)val * invDen % MOD;
        }

        long long nmod = n % MOD;
        long long pval = 0;
        long long pw = 1;
        for (int j = 0; j <= K; ++j) {
            pval = (pval + (__int128)b[j] * pw) % MOD;
            pw = (__int128)pw * nmod % MOD;
        }

        long long rn = modpow(r, n);
        long long ans = ((__int128)rn * pval - b[0]) % MOD;
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }

    return 0;
}