Разбор
Tutorial is loading...
Код решения (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
int r = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
r += x;
cout << r / m << ' ';
r %= m;
}
cout << '\n';
return 0;
}
Разбор
Tutorial is loading...
Код решения (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 1000 + 7;
int pr[N];
bool ok[N];
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
string s, t;
static char buf[N];
scanf("%s", buf);
s = buf;
scanf("%s", buf);
t = buf;
pr[0] = 0;
forn(i, n - m + 1){
bool fl = true;
forn(j, m)
if (s[i + j] != t[j])
fl = false;
ok[i] = fl;
pr[i + 1] = pr[i] + ok[i];
}
for (int i = max(0, n - m + 1); i < n; ++i){
pr[i + 1] = pr[i];
}
forn(i, q){
int l, r;
scanf("%d%d", &l, &r);
--l, r -= m - 1;
printf("%d\n", r >= l ? pr[r] - pr[l] : 0);
}
return 0;
}
Разбор
Tutorial is loading...
Код решения (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = 300 * 1000 + 9;
int n;
int a[2][N];
long long sum123[2][N];
long long sum321[2][N];
long long sum111[2][N];
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < 2; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &a[i][j]);
for(int i = 0; i < 2; ++i)
for(int j = n - 1; j >= 0; --j){
sum123[i][j] = sum123[i][j + 1] + (j + 1) * 1LL * a[i][j];
sum321[i][j] = sum321[i][j + 1] + (n - j) * 1LL * a[i][j];
sum111[i][j] = sum111[i][j + 1] + a[i][j];
}
/* for(int i = 0; i < 2; ++i)
for(int j = n - 1; j >= 0; --j){
cout << i << ' ' << j << " : ";
cout << sum123[i][j] << " " << sum321[i][j] << " " << sum111[i][j] << endl;
} */
long long res = 0, sum = 0;
for(int i = 0, j = 0; j < n; ++j, i ^= 1){
long long nres = sum;
nres += sum123[i][j] + j * 1LL * sum111[i][j];
nres += sum321[i ^ 1][j] + (j + n) * 1LL * sum111[i ^ 1][j];
res = max(res, nres);
sum += a[i][j] * 1ll * (j + j + 1);
sum += a[i ^ 1][j] * 1ll * (j + j + 2);
}
for(int j = 0; j < n; ++j) res -= a[0][j] + a[1][j];
printf("%I64d\n", res);
return 0;
}
Разбор
Tutorial is loading...
Код решения (Ajosteen)
#include <bits/stdc++.h>
#include "testlib.h"
using namespace std;
const int N = 109;
int n, m;
int a[N], b[N];
int res[N][N];
int main() {
int cur = 0;
cin >> n >> m;
for(int i = 0; i < n; ++i)
cin >> a[i], cur ^= a[i];
for(int i = 0; i < m; ++i)
cin >> b[i], cur ^= b[i];
if(cur != 0){
puts("NO");
return 0;
}
puts("YES");
for(int i = 1; i < m; ++i)
cur ^= b[i];
cur ^= a[0];
cout << cur << ' ';
for(int i = 1; i < m; ++i)
cout << b[i] << ' ';
cout << endl;
for(int i = 1; i < n; ++i){
cout << a[i] << ' ';
for(int j = 1; j < m; ++j)
cout << 0 << ' ';
cout << endl;
}
return 0;
}
Разбор
Tutorial is loading...
Код решения (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const double EPS = 1e-9;
const int N = 200 * 1000 + 555;
li sy, a, b;
int n, q;
pt s[N], p[N];
inline bool read() {
if(!(cin >> sy >> a >> b))
return false;
assert(cin >> n);
fore(i, 0, n)
assert(scanf("%lld%lld", &s[i].x, &s[i].y) == 2);
assert(cin >> q);
fore(i, 0, q)
assert(scanf("%lld%lld", &p[i].x, &p[i].y) == 2);
return true;
}
int getGE(ld x) {
for(int pos = max(int(lower_bound(s, s + n, pt(li(x), -1)) - s) - 2, 0); pos < n; pos++)
if(x <= s[pos].x)
return pos;
return n;
}
li ps[N];
li getSum(int l, int r) {
li ans = r > 0 ? ps[r - 1] : 0;
ans -= l > 0 ? ps[l - 1] : 0;
return ans;
}
inline void solve() {
fore(i, 0, n) {
ps[i] = s[i].y - s[i].x;
if(i > 0)
ps[i] += ps[i - 1];
}
fore(i, 0, q) {
ld lx = p[i].x + (a - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
ld rx = p[i].x + (b - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
int posL = getGE(lx);
int posR = getGE(rx) - 1;
ld sum = getSum(posL, posR);
if(posL > 0)
sum += max(ld(0.0), s[posL - 1].y - max((ld)s[posL - 1].x, lx));
if(posR >= 0)
sum += max(ld(0.0), min((ld)s[posR].y, rx) - s[posR].x);
sum *= ld(p[i].y - sy) / p[i].y;
printf("%.15f\n", double(sum));
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Разбор
Tutorial is loading...
Код первого решения (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const long long INF64 = (long long)(1e18);
const int N = 1000 * 1000 + 13;
int n, m;
vector<pair<int, int>> g[N];
long long d[N];
int siz[N];
int tin[N], tout[N], T;
int pr[N];
void calc(int v, int p){
pr[v] = p;
tin[v] = T++;
siz[v] = 1;
for (auto it : g[v]){
int u = it.first;
int w = it.second;
if (u == p) continue;
d[u] = d[v] + w;
calc(u, v);
siz[v] += siz[u];
}
tout[v] = T++;
}
inline int isp(int v, int u){
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
long long dif;
long long mn;
void dfs(int v, int p){
dif = min(dif, max(0ll, -(mn - d[v])));
if (p != -1 && pr[p] != -1)
dif = min(dif, max(0ll, -(d[pr[p]] - d[v])));
for (auto it : g[v]){
int u = it.first;
int w = it.second;
if (u == p) continue;
if (!isp(u, n - 1)){
dif = min(dif, max(0ll, -(mn + w - d[v])));
mn = max(mn, w + d[v]);
if (p != -1)
dif = min(dif, max(0ll, -(w - d[v] + d[p])));
}
}
for (auto it : g[v]){
int u = it.first;
if (u == p) continue;
if (isp(u, n - 1))
dfs(u, v);
}
}
int main() {
scanf("%d%d", &n, &m);
forn(i, n - 1){
int v, u, w;
scanf("%d%d%d", &v, &u, &w);
--v, --u;
g[v].push_back(make_pair(u, w));
g[u].push_back(make_pair(v, w));
}
T = 0;
calc(0, -1);
long long cur = d[n - 1];
dif = INF64;
mn = -INF64;
forn(i, n)
if (!isp(i, n - 1) && siz[i] > 1)
dif = 0;
if (dif > 0)
dfs(0, -1);
forn(i, m){
int x;
scanf("%d", &x);
printf("%lld\n", min(cur, cur - dif + x));
}
return 0;
}
Код второго решения (BledDest)
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > g;
vector<long long> d;
vector<long long> d1;
vector<long long> dn;
int n, q;
bool read()
{
scanf("%d %d", &n, &q);
g.resize(n);
d.resize(n);
for(int i = 0; i < n - 1; i++)
{
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
--x;
--y;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
return true;
}
void dfs(int x, int p = -1, long long dist = 0)
{
d[x] = dist;
for (auto e : g[x])
if (p != e.first)
dfs(e.first, x, e.second + dist);
}
void solve()
{
dfs(0);
d1 = d;
dfs(n - 1);
dn = d;
set<pair<long long, int> > dists_n;
vector<pair<long long, int> > order;
for(int i = 0; i < n; i++)
order.push_back(make_pair(d1[i] - dn[i], i));
sort(order.begin(), order.end());
for(int i = 0; i < n; i++)
dists_n.insert(make_pair(dn[i], i));
vector<int> pos(n);
for(int i = 0; i < n; i++)
pos[order[i].second] = i;
long long T = (long long)(1e18);
for(int i = 0; i < n; i++)
{
int v = order[i].second;
dists_n.erase(make_pair(dn[v], v));
for (auto e : g[v])
if (pos[e.first] > pos[v])
dists_n.erase(make_pair(dn[e.first], e.first));
if (!dists_n.empty())
T = min(T, d1[n - 1] - d1[v] - dists_n.rbegin()->first);
for (auto e : g[v])
if (pos[e.first] > pos[v])
dists_n.insert(make_pair(dn[e.first], e.first));
}
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
printf("%lld\n", d1[n - 1] - max(0ll, T - x));
}
}
int main()
{
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
if (read())
{
solve();
}
}
Разбор
Tutorial is loading...
Код решения (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const int N = 200 * 1000 + 555;
int n; li x, y;
li a[N];
inline bool read() {
if(!(cin >> n >> x >> y))
return false;
fore(i, 0, n)
assert(scanf("%lld", &a[i]) == 1);
return true;
}
li gcd(li a, li b) {
while(a > 0) {
b %= a;
swap(a, b);
}
return b;
}
vector<pt> factorize(li v) {
vector<pt> f;
for(li x = 2; x <= 1'000'000 && x * x <= v; x++) {
int cnt = 0;
while(v % x == 0)
v /= x, cnt++;
if(cnt > 0)
f.emplace_back(x, cnt);
}
if(v > 1) {
for(li s = max(1ll, (li)sqrtl(v) - 2); s * s <= v; s++)
if(s * s == v) {
f.emplace_back(s, 2);
v = 1;
break;
}
if(v > 1) {
vector<li> cnd(a, a + n);
cnd.push_back(x);
cnd.push_back(y);
for(li c : cnd) {
li g = gcd(v, c);
if(g != 1 && g != v) {
li a = g, b = v / g;
if(a > b)
swap(a, b);
f.emplace_back(a, 1);
f.emplace_back(b, 1);
v = 1;
break;
}
}
if(v > 1)
f.emplace_back(v, 1), v = 1;
}
}
return f;
}
int d[(1 << 18) + 3];
inline void solve() {
if(y % x != 0) {
puts("0");
return;
}
vector<pt> fy = factorize(y);
vector<pt> fx;
li cx = x;
for(auto p : fy) {
int cnt = 0;
while(cx % p.x == 0)
cx /= p.x, cnt++;
fx.emplace_back(p.x, cnt);
}
vector<li> ps;
vector<pt> bb;
fore(i, 0, sz(fy)) {
if(fx[i].y < fy[i].y) {
ps.push_back(fy[i].x);
bb.emplace_back(fx[i].y, fy[i].y);
}
}
fore(i, 0, n) {
if(a[i] % x != 0)
continue;
int mask = 0;
li ca = a[i];
fore(j, 0, sz(ps)) {
int cnt = 0;
while(ca % ps[j] == 0)
ca /= ps[j], cnt++;
assert(cnt >= bb[j].x);
mask |= (cnt > bb[j].x) << j;
}
d[mask]++;
}
for(int i = 0; i < sz(ps); i++) {
fore(mask, 0, 1 << sz(ps))
if((mask >> i) & 1)
d[mask] += d[mask ^ (1 << i)];
}
li ans = 0;
fore(i, 0, n) {
if(y % a[i] != 0)
continue;
int mask = 0;
li ca = a[i];
fore(j, 0, sz(ps)) {
int cnt = 0;
while(ca % ps[j] == 0)
ca /= ps[j], cnt++;
assert(cnt <= bb[j].y);
mask |= (cnt < bb[j].y) << j;
}
ans += d[mask ^ ((1 << sz(ps)) - 1)];
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Can someone prove/find a countercase for my solution for D? 41174052
I upsolved D in the same manner. Will try to explain the logic behind it [Since the editorial simply left it to the reader to find its proof]
Let r,c be the dimensions of the matrix, row[1..r] be the row wise xor value array, col[1..c] be the column-wise xor value array.
Temporarily, forget a[1][1]. Fill a[1][2] with col[2], a[1][3] with col[3] and so on.. So everything except col[1] is satisfied right now. (We are filling the first row, except the first element, with values from col array)
Similarly, fill a[2][1] with row[2], a[2][3] with row[3] and so on.. Everything except row[1] is satisfied right now (We are filling the first column, except the first element, with values from row array)
Now we have a[1][1] left. Based on the values we filled right now, the current xor value of the first row in our matrix is col[2]^col[3]^..col[c]. This value, can also be represented as C^col[1], where C = total xor of the col array (col[1]^col[2]^..col[c]).. We know that the xor value of elements in first row should be row[1]. Hence, if a[1][1] is equal to C^col[1]^row[1], our answer satisfies all the stipulated properties.
What if we had done it the other way round? Lets check that out. Based on the values we filled right now, the current xor value of the first column in our matrix is row[2]^row[3]^..row[r]. This value, can also be represented as R^row[1], where R = total xor of the row array (row[1]^row[2]^..row[r]).. We know that the xor value of elements in first column should be col[1]. Hence, if a[1][1] is equal to R^row[1]^col[1], our answer satisfies all the stipulated properties.
If we had chosen either of the above options, it would still be the same value. Its because R=C!
How can we be sure this always identifies an impossible case? E.g what if using some other strategy you can make a matrix when this method returns "NO"?
The initial check, about R not being equal to C (refer my first comment for notations), is enough for the impossible condition.
R will have each element represented once, while C will have each elemented represented once. Xor-ing these two values should give zero.
Hence, checking for this condition and then proceeding with this algorithm of filling the first row and first column alone, and leaving the other elements as zero is a good enough solution.
Forgive me if I misunderstood your question.
What if there is some case where you can fill some of the 0's such that an input you deemed "impossible" is possible. My question is how can you prove this case does not exist, because of course it works when there is a valid matrix, but how can we be sure it always identifies impossible case.
I waited for this to be explained in editorial, and I'm a bit disappointed they didn't even mention it.
You haven't given the proof rather you have explained the obvious thing. If you know the thing what @burdy said then please share otherwise the above thing of yours is just like some irrevelant stuff which I think everybody knows already :xD.
In problem D... Why if xor of a1 a2 ...an != to xor of b1 b2 ...bm the answer is no??
Because
is xor of all elements in matrix, and
is xor of all elements in matrix. So they must be equal.
Could someone explain to me the logic behind exercise — C? I can't seem to understand it,even after reading the editorial.
Let first you have to move in a zigzag pattern then go right to end and then left where you stop zigzag pattern.(it's cover all case) Key point is if you start moving in straight line you can't allow to move in zigzag pattern again only one 'U' turn at end.(think why?)
So you can stop zigzag pattern at 1,2,3,...,N-1.For each value where you stop zigzag pattern (1<=i<=N-1) . You can find total weight of the collected mushrooms in O(1) by help of sum123, sum321 and sum111.
Thanks for the help, but one more thing, what values does Sum123,Sum321,Sum111 contain ?
For that see Editorial.
Ok, thanks for the tips :-))
that 3 arrays is like suffix sum array. ex: a[1,2,3,4] ss[10,9,7,4] at 1<='i'<=n we save sum of i to n;
but in this case we make suffix weight.
Problem D can be solved with Gaussian Elimination. This way the solution is more straightforward.
can you elaborate?
Since a[i], b[i] <= 10E9, for each number in the table, there are at most 30 bits, and each bit is independent from others. I mean, the k-th bit of c[i][j] has nothing to do with (k + 1)-th bit, etc.
Consider k-th bits of all c[i][j]. Let denote that b[k][i][j] = 1/0.
Now you can see that we have a system of n + m linear equations such that:
(b[k][1][1] + b[k][1][2] + ... b[k][1][m]) % 2 = k-th bit of a1
...
(b[k][n][1] + b[k][n][2] + ... b[k][n][m]) % 2 = k-th bit of a[n]
(b[k][1][1] + b[k][2][1] + ... b[k][n][1]) % 2 = k-th bit of b[1]
...
(b[k][1][m] + b[k][2][m] + ... b[k][n][m]) % 2 = k-th bit of b[m]
This way, it makes sense that a solution of this system of equations is also a solution for all k-th bits of c[i][j]. In order to find a solution, use Gaussian Elimination. Since there are 30 bits, do this 30 times :)
Here is my AC code 41183870
In my code, in order to implement easily, I assume that every equation has n + m variables. However, if the variable is unnecessary for the equation (for instance, b[k][2][1] is unnecessary for (*)), let the coefficient 0, otherwise 1.
In addition, since the eliminating process is the same for all bits, I list all bits at once and do the eliminating process once only.
In problem C what if we were not allowed to fill 0 as an entry i.e. if 1<=c<=2*10^9 ??
Can someone please explain how to implement problem C ?
Thanks.
There's a bug in test data in Problem F:
There is an Accepted Submission: 41232049
The test data:
correct answer should be : 100(link the vertex 1 and 3)
but its answer is: 3
That's called an incomplete testset, not bugged. Just a missed possibility for the hack.
Sorry for my poor English,⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄
So will the test data be updated?or still incomplete ?
It has been added. Previous submissions are not retested, obviously, but this test will present for the further ones.
Can someone explain me how
sum111
is handling the growth of the mushrooms in Problem C.sum111[i] is the total speed of mushroom growth in the cells on segment [i .. n].
So, for example, if we start collecting mushrooms on segment [i .. n] in time moment 2i — 2, then we add to the answer the value of sum123[i] + sum111[i] * (2i — 2).
Someone, please correct me if I am wrong but can the top left element be also set as
b1 ^ a2 ^ a3 ^ ... ^ an
in problem D .Since
a1 ^ a2 ^...^ an = b1 ^ b2 ^...^ bm
, so, of course,a1 ^ b2 ^...^ bm = b1 ^ a2 ^...^ an
.There are two announcements and two tutorials link in problems page.
awoo
It's interesting that the second solution for F works even without the restriction that the input graph is a tree. Have you used the same technique before for other problems?
That's really interesting, I didn't even see that.
In fact, it will be better if I address this question to vovuh because he actually proposed this idea in problem F (and I just implemented the solution and handled the fact that the edges we add are bidirectional).
Wow! Such an interesting fact. Well, I haven't used this idea earlier (I suppose). I came up with it while I thought about a shortest paths graph condition (for the edge (x, y) it is true that this edge is in the shortest paths graph iff d1x + w(x, y) + dny = d1n or d1y + w(x, y) + dnx = d1n, it is well known equation). And I decided that it also can be true for the general case, but I haven't thought about it.
Why is Binary Search giving me TLE in Proble 1016E — Rest In The Shades ?
http://codeforces.net/contest/1016/submission/41256720
I think there's no better solution than O(log n) per query.
Please help !!!!
try using scanf and printf the timlimit is to hard for this one i believe... i only got AC with scanf and printf too
It was mentioned in the other thread that reading
integers
asdoubles
withcin
slows down solution greatly.The graph for problem F can be further restricted: its a path between 1 and n where every vertex on the path has at most one additional child wich is a leaf. (in every other case there would be 3 vertices connected by two edges which are not on the 1 to n path. Adding a third edge to this triangle would not change the shortest path as the added edge cant even lie on any simple path between 1 and n)
There's a typo in the tutorial for problem C. Instead of the ai s, we have ak s. I'm mentioning this because I initially got confused while reading the expressions in the tutorial.
Someone can explain to me why we do exactly this
pr[i + 1] = pr[i] + ok[i];
and this--l, r -= m - 1;
in problem B? This is not clear to meThe first one is prefix sums. https://www.hackerrank.com/topics/prefix-sum
For the second one: Since t is of length m, within the segment [l, r], the last position where it can start from is r-(m-1), So, we only count the occurences of t between [l, r-(m-1)]
Can someone explain the statement for(int i = 0, j = 0; j < n; ++j, i ^= 1) in problem1016C
it is equivalent to
In Problem C's editorial,
"Let's iterate on the number of columns Vasya will pass in a zigzag pattern and maintain the weight of mushrooms he will collect while doing so."
How exactly we know which zigzag path we have to take and upto where ?
Firstly, we can observe that there are exactly (n + 1) ways to go through the grid
Ill express the coordinate using the format (row_num, col_num)
The first scenario is to from (1,1) to (1,n) then to(2,n) then to (2, 1) (Sample Input 1)
The second scenario is a zig-zag pattern (Sample Input 2)
The rest is by combining the two.
Any other scenario will block the previous cell and disconnects the grid
Example:
n = 3
(1,1) -> (1,2) -> (2,2) -> (2,3) -> (1,3)
Obviously, all path to (2,1) is blocked
With the above conclusion, we can use Dynamic Programming to precompute the prefix sum and calculate the answer
Many thanks! That helped clear the cloud of ignorance in my thinking pattern. "Any other scenario will block the previous cell and disconnects the grid" — this line hit me so hard, i realized where i was stuck.
Maybe there's an easier solution for D. The matrix could be
b[1] b[2] …… b[m-1] (a[1] xor b[1] xor b[2]……b[m-1])
0 0 …… 0 a[2]
0 0 …… 0 a[3]
....
0 0 …… 0 a[n]
Because (a[1] xor b[1] ...b[m-1]) xor a[2]...a[n] = b[m], so it is a possible solution
basically it is the same solution
Could you please provide any proof or explain the problem why such arrangement will provide a correct answer ?
it is written in editorial
1016A - Тетрадь Смерти
Can someone please explain to me why 'l' is decremented in the last for loop?
And also it would be much appreciated if you explain for any value x, what does pr[x] stand for? From the above code, I guess pr[x] represents the number of times string 't' appears in s[1, x+|m|-1].
First, see prefix sum : https://www.hackerrank.com/topics/prefix-sum
And decrementing of l because the input is given 1 based while we work zero based in our arrays.
Second, hope looking at it from the other side clears it up. So here's my approach. You'll find prefix sum of occurrences of string t in s but instead of marking the start positions of the string, you'll mark the end positions.
For example, in the first test case looking for
for
incodeforces
the prefix array will look like thisc o d e f o r c e s
0 0 0 0 0 0 1 1 1 1
now pre[i] means number of occurrences of string t in string s in [0, i]. This is consistent with given r but we need to push l (m-1) positions. now you have pre[r] and pre[l+m-1]. To get what's in between them you substract pre[r] — pre[(l+m-1) — 1].
Hopefully this clears it up also see my code 41592407 for further understanding
I've gone through your solution thoroughly and understood how you actually stored number of occurrences of string t in prefix sum array using the end index, that way it makes the range clearer! Thanks a lot for your help Bekh :)
Glad it helped :). Keep coding!
There's no need to do prime factorization in problem G, it can be solved in true polynomial time. Just factor $$$Y$$$ relative to numbers $$$a_1, \ldots, a_n, X$$$. By relative factorization I mean, represent $$$Y = f_1^{b_1} \cdots f_k^{b_k}$$$, where $$$f_i$$$ are pairwise coprime and for each $$$r \in a \cup X$$$, $$$GCD(r, f_i)$$$ is either $$$1$$$ or $$$f_i$$$. This factorization can be easily found by starting with $$$[Y]$$$ and refining it with each element of $$$a \cup X$$$. Finally you can safely use this factorization instead of the true prime factorization of $$$Y$$$ in the same way as in the editorial.
Sample code: 82648734