HackerRank Algebra – Rational Sums

Challenge: Rational Sums

Subdomeniu: Algebra (algebra)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464763752

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/rational-sums/problem

Cerinta

Today Konstantin learned about convergence of series. For instance, series  
$$ \sum\limits_{n = 1}^{\infty}\frac1{n(n+1)} = \frac12 + \frac16 + \frac1{12} + \dots = 1, $$ 
$$ \sum\limits_{n = 1}^{\infty}\frac1{n^2} = 1 + \frac14 + \frac19 + \frac1{16} + \dots = \frac{\pi^2}{6}, $$ converge, while 
$$ \sum\limits_{n = 1}^{\infty}\frac1n = 1 + \frac12 + \frac13 + \frac14 + \dots = +\infty $$ diverges. See more at https://en.wikipedia.org/wiki/Convergent_series .

As you may note, some simple looking series can converge to quite complicated numbers, like $\frac{\pi^2}6$, $e$, etc. Konstantin noted this and decided to study only special case of rational functions sums, that is  

$$ \sum\limits_{n = 1}^{\infty}\frac{P(n)}{Q(n)}, $$ where $P$ and $Q$ are polynomials and $Q(n)\not=0$ for positive integer $n$. It can be proven that if $\deg P \leq \deg Q - 2$ the series converges. But, as example $\sum\limits_{n = 1}^{\infty}\frac1{n^2} $ shows, sum of rational functions can be irrational. 

After some time, Konstantin decided to consider some very special case of rational functions when $$ Q(x) = (x + a_1)(x + a_2)\dots(x + a_m) $$ and $$P(x) = b_0 + b_{1}x + \dots + b_{n-2}x^{m - 2}, $$ with constraint that $a_1, a_2, \dots, a_m$ are _distinct_ non-negative integers. Fortunately, it can be proven that in this case sum of the series above is rational number. Now Konstantin want you to calculate it.

Input Format

The first line of input contains single integer, $m$. The next line contains $m$ integers $a_1, a_2, \dots, a_m$, separated by space. The next line contains $m - 1$ integers $b_0, b_1, \dots, b_{m-2}$.

Output Format

If answer is irreducible fraction $\frac{a}{b}$, print $ab^{-1} \bmod (10^9 + 7)$, where $b^{-1}$ is multiplicative inverse of $b$ modulo $10^9 + 7$. It is guaranteed that $b \mod 10^9 + 7 \not=0$.

Constraints

+ $2 \leq m \leq 5000,$  
+ $0\leq a_i \leq 5000,$  
+ $0 \leq b_i \leq 10^9$.  
+ $a_1, \dots, a_m$ are distinct. 

**Subtasks**  

Solutions that works correctly for $m\leq 100$ will score at least $50\%$ of points.

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 m;
    cin >> m;
    vector<int> a(m);
    int maxA = 0;
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        maxA = max(maxA, a[i]);
    }

    vector<long long> b(m - 1);
    for (int i = 0; i < m - 1; ++i) {
        cin >> b[i];
        b[i] %= MOD;
    }

    // Harmonic numbers H[k] = sum_{t=1}^k 1/t mod MOD
    vector<long long> H(maxA + 1, 0);
    for (int k = 1; k <= maxA; ++k) {
        H[k] = H[k - 1] + modpow(k, MOD - 2);
        if (H[k] >= MOD) H[k] -= MOD;
    }

    auto evalP = [&](int x) {
        long long xm = x % (int)MOD;
        if (xm < 0) xm += MOD;
        long long val = 0;
        for (int i = m - 2; i >= 0; --i) {
            val = ((__int128)val * xm + b[i]) % MOD;
        }
        return val;
    };

    long long ans = 0;

    for (int i = 0; i < m; ++i) {
        long long num = evalP(-a[i]);

        long long den = 1;
        for (int j = 0; j < m; ++j) if (j != i) {
            long long d = (a[j] - a[i]) % MOD;
            if (d < 0) d += MOD;
            den = (__int128)den * d % MOD;
        }

        long long ci = (__int128)num * modpow(den, MOD - 2) % MOD;
        ans = (ans + (__int128)ci * H[a[i]]) % MOD;
    }

    ans = (MOD - ans) % MOD; // S = -sum c_i * H[a_i]
    cout << ans << '\n';
    return 0;
}