Soluție HackerRank pentru Fun With Series, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Fun With Series
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Fun With Series
Subdomeniu: Algebra (algebra)
Scor cont: 75.0 / 75
Submission status: Accepted
Submission score: 1.0
Submission ID: 464779714
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/fun-with-series/problem
Cerință
Julia found a series, G, defined as:
G_n = begin{cases}0 &n = 01 &n = 1a× G_n-1+b× G_n-2 & ngt 1 text{ and } a, b ≥ 1 end{cases}
For some integer p (where p gt 0), she finds p + 2 integers, c_0, c_1, c_2, …, c_p+1, such that L(p, n) = 0 holds for all integers n (where n gt p):
L(p, n) = ∑_i = 0^p + 1 c_i ≤ft(G_n-iright)^p
She realized that the values of c_i are not unique, so she only considers the tuple (c_0, c_1, …, c_p+1) such that c_0 gt 0 and c_0 is minimal. It is guaranteed that when c_0 gt 0 and c_0 is minimal, there exists only one tuple (c_0, c_1, …, c_p+1).
Next, she defines S_1(p) and S_2(p):
S_1(p) = ≤ft( ∑ c_i right) % (10^9+7) forall c_i > 0
S_2(p) = ≤ft( ∑ ≤ft|c_i right| right) % (10^9+7) forall c_i < 0
She then finds the following interesting property of c_i:
prod_i=0^p+1 ≤ft|c_iright| = w × prod_i=2^p+1 G_i^z_i
where w and z_i are integers such that:
* w ne 0
* z_2 + 2p = z_p + 1 + 2
* ∑limits_i=2^p+1 z_i = p
Julia wants you to answer q queries in the following forms:
1. `1 l r`: Using S_1(p) and S_2(p), print three space-separated integers denoting the respective values of Count_1, Count_2, and Count_3 where:
* Count_1 is the total number of possible values of p (where l ≤ p ≤ r) such that S_1(p) gt S_2(p).
* Count_2 is the total number of possible values of p (where l ≤ p ≤ r) such that S_1(p) lt S_2(p).
* Count_3 is the total number of possible values of p (where l ≤ p ≤ r) such that S_1(p) = S_2(p).
2. `2 p u v`: Find the value of S modulo ≤ft(10^9+7right):
S = ≤ft(prod_i=u^vG_iright)^≤ft(w + phiright) text{, where } phi=≤ft|∑_i=u^v z_iright|
Input Format
The first line contains three space-separated integers describing the respective values of a, b, and q.
Each line i of the q subsequent lines contains three or four space-separated values denoting a query asked by Julia.
Output Format
Print q lines of output where each line i denotes the answer to query i.
Constraints
* 1 ≤ a, b ≤ 10^6
* 1 ≤ q ≤ 5 × 10^4
* 1 ≤ l ≤ r ≤ 10^3
* 1 ≤ p ≤ 10^6
* 2 ≤ u ≤ v ≤ p + 1
Cod sursă
#include <bits/stdc++.h>
using namespace std;
static const long long MOD = 1000000007LL;
struct Query {
int type;
long long x, y, z; // type1: x=l, y=r; type2: x=p, y=u, z=v
};
static long long modPow(long long a, long long e, long long mod) {
a %= mod;
long long r = 1 % mod;
while (e > 0) {
if (e & 1) r = (__int128)r * a % mod;
a = (__int128)a * a % mod;
e >>= 1;
}
return r;
}
static long long modInv(long long a) {
return modPow(a, MOD - 2, MOD);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
int q;
cin >> a >> b >> q;
vector<Query> queries;
queries.reserve(q);
int maxR = 0;
int maxP = 0;
int maxV = 1;
for (int i = 0; i < q; i++) {
int t;
cin >> t;
if (t == 1) {
long long l, r;
cin >> l >> r;
queries.push_back({t, l, r, 0});
maxR = max<long long>(maxR, r);
} else {
long long p, u, v;
cin >> p >> u >> v;
queries.push_back({t, p, u, v});
maxP = max<long long>(maxP, p);
maxV = max<long long>(maxV, v);
}
}
int N = maxR + 1;
N = max(N, 1);
int G = max(maxV, N + 2);
vector<int> g(G + 1, 0);
g[0] = 0;
g[1] = 1;
for (int i = 2; i <= G; i++) {
long long val = ((__int128)(a % MOD) * g[i - 1] + (__int128)(b % MOD) * g[i - 2]) % MOD;
g[i] = (int)val;
}
vector<long long> prefProd(G + 1, 1);
for (int i = 1; i <= G; i++) {
prefProd[i] = (prefProd[i - 1] * g[i]) % MOD;
}
vector<vector<int>> tria(N + 2, vector<int>(N + 2, 0));
if (N >= 1) {
tria[1][0] = 1;
tria[1][1] = 1;
}
for (int i = 2; i <= N; i++) {
tria[i][0] = 1;
long long rpow = 1;
for (int j = 1; j <= i; j++) {
long long term1 = ((__int128)tria[i - 1][j - 1] * g[i - j + 1]) % MOD;
term1 = (term1 * rpow) % MOD;
long long term2 = ((__int128)tria[i - 1][j] * g[j - 1]) % MOD;
term2 = (term2 * (b % MOD)) % MOD;
tria[i][j] = (int)((term1 + term2) % MOD);
rpow = (rpow * (b % MOD)) % MOD;
}
}
vector<int> pref0(N + 2, 0), pref1(N + 2, 0), pref2(N + 2, 0);
auto isSn = [](int j) -> bool {
int m = j & 3;
return (m == 1 || m == 2);
};
for (int i = 1; i <= N; i++) {
int sp = 0, sn = 0;
for (int j = 0; j <= i; j++) {
if (isSn(j)) {
sn += tria[i][j];
if (sn >= MOD) sn -= MOD;
} else {
sp += tria[i][j];
if (sp >= MOD) sp -= MOD;
}
}
pref0[i] = pref0[i - 1];
pref1[i] = pref1[i - 1];
pref2[i] = pref2[i - 1];
if (sn == sp) pref1[i]++;
else if (sn > sp) pref2[i]++;
else pref0[i]++;
}
for (auto &qq : queries) {
if (qq.type == 1) {
int L = (int)qq.x + 1;
int R = (int)qq.y + 1;
L = max(L, 1);
R = min(R, N);
int ans0 = pref0[R] - pref0[L - 1];
int ans2 = pref2[R] - pref2[L - 1];
int ans1 = pref1[R] - pref1[L - 1];
cout << ans0 << " " << ans2 << " " << ans1 << "\n";
} else {
long long p = qq.x;
int u = (int)qq.y;
int v = (int)qq.z;
long long prod_uv = prefProd[v] * modInv(prefProd[u - 1]) % MOD;
long long wp = p * (p + 1) * (p + 2) / 6;
long long w = modPow((b % (MOD - 1) + (MOD - 1)) % (MOD - 1), wp, MOD - 1);
long long phi = 1LL * v * (v - 1) - 1LL * (u - 1) * (u - 2) - 1LL * p * (v - u + 1);
phi = llabs(phi);
phi = (phi + w) % (MOD - 1);
cout << modPow(prod_uv, phi, MOD) << "\n";
}
}
return 0;
}