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
Cerinta
Julia found a series, $G$, defined as:
$$G_n = \begin{cases}0 &n = 0\\1 &n = 1\\a\times G_{n-1}+b\times G_{n-2} & n\gt 1 \text{ and } a, b \ge 1 \end{cases}$$
For some integer $p$ (where $p \gt 0$), she finds $p + 2$ integers, $c_0,\ c_1,\ c_2, \ldots,\ c_{p+1}$, such that $L(p, n) = 0$ holds for all integers $n$ (where $n \gt p$):
$$L(p,\ n) = \sum_{i = 0}^{p + 1} c_i \left(G_{n-i}\right)^p$$
She realized that the values of $c_i$ are not unique, so she only considers the tuple $(c_0,\ c_1, \ldots,\ 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, \ldots,\ c_{p+1})$.
Next, she defines $S_1(p)$ and $S_2(p)$:
$$S_1(p) = \left( \sum c_i \right) \% (10^9+7)\ \ \ \ \ \forall c_i > 0$$
$$S_2(p) = \left( \sum \left|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} \left|c_i\right| = w \times \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$
* $\sum\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 \le p \le r$) such that $S_1(p) \gt S_2(p)$.
* $Count_2$ is the total number of possible values of $p$ (where $l \le p \le r$) such that $S_1(p) \lt S_2(p)$.
* $Count_3$ is the total number of possible values of $p$ (where $l \le p \le r$) such that $S_1(p) = S_2(p)$.
2. `2 p u v`: Find the value of $S$ modulo $\left(10^9+7\right)$:
$$S = \left(\prod_{i=u}^{v}G_i\right)^{\left(w + \phi\right)} \text{, where } \phi=\left|\sum_{i=u}^{v} z_i\right|$$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 \le a,\ b \le 10^6$
* $1 \le q \le 5 \times 10^4$
* $1 \le l \le r \le 10^3$
* $1 \le p \le 10^6$
* $2 \le u \le v \le p + 1$Cod sursa
#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;
}
HackerRank Algebra – Fun With Series