Soluție HackerRank pentru Summing the K-N-R Series, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Summing the K-N-R Series
- Domeniu: Algebra
- Limbaj: C++14
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
Cerință
You are given a sequence whose n^{text{th}} term is
T_n = n^K × R^n
You have to evaluate the series
S_n = T_1 + T_2 + T_3 + ·s + 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 ≤ T ≤ 10
1 ≤ K ≤ 10^3
1 ≤ n ≤ 10^16
2 ≤ R ≤ 10^16
Rbmod (10^9 + 7) not= 1
Sample Input
2
2
5
2
3
4
3
Sample Output
1146
5988
Explanation
Case 1: 1146 = 1^2× 2^1 + 2^2× 2^2 + 3^2× 2^3 + 4^2× 2^4 + 5^2× 2^5
Case 2: 5988 = 1^3× 3^1 + 2^3× 3^2 + 3^3× 3^3 + 4^3× 3^4
Cod sursă
#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;
}